Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets

Abstract : Given a planar convex set C, we give sublinear approximation algorithms to determine approximations of the largest axially symmetric convex set S contained in C, and the smallest such set S′ that contains C. More precisely, for any var epsilon>0, we find an axially symmetric convex polygon Qsubset ofC with area |Q|>(1−var epsilon)|S| and we find an axially symmetric convex polygon Q′ containing C with area |Q′|<(1+var epsilon)|S′|. We assume that C is given in a data structure that allows to answer the following two types of query in time TC: given a direction u, find an extreme point of C in direction u, and given a line ℓ, find C∩ℓ. For instance, if C is a convex n-gon and its vertices are given in a sorted array, then TC=O(logn). Then we can find Q and Q′ in time O(var epsilon−1/2TC+var epsilon−3/2). Using these techniques, we can also find approximations to the perimeter, area, diameter, width, smallest enclosing rectangle and smallest enclosing circle of C in time O(var epsilon−1/2TC).
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.inrae.fr/hal-02655641
Déposant : Migration Prodinra <>
Soumis le : vendredi 29 mai 2020 - 22:41:23
Dernière modification le : vendredi 12 juin 2020 - 10:43:26

Identifiants

Collections

Citation

Hee-Kap Ahn, Peter Brass, Otfried Cheong, Hyeon-Suk Na, Chan-Su Shin, et al.. Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets. Computational Geometry, Elsevier, 2006, 33 (3), pp.152-164. ⟨10.1016/j.comgeo.2005.06.001⟩. ⟨hal-02655641⟩

Partager

Métriques

Consultations de la notice

11