Please use this identifier to cite or link to this item:
Title: Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets
Authors: Ahn, H.-K.
Brass, P.
Cheong, O.
Na, H.-S.
Shin, C.-S.
Vigneron, A. 
Keywords: Approximation
Axial symmetry
Shape matching
Issue Date: 2006
Citation: Ahn, H.-K., Brass, P., Cheong, O., Na, H.-S., Shin, C.-S., Vigneron, A. (2006). Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets. Computational Geometry: Theory and Applications 33 (3) : 152-164. ScholarBank@NUS Repository.
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 ε>0, we find an axially symmetric convex polygon Q⊂C with area |Q|>(1-ε)|S| and we find an axially symmetric convex polygon Q′ containing C with area |Q′|<(1+ε)|S′|. We assume that C is given in a data structure that allows to answer the following two types of query in time C T: 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 C T=O(logn). Then we can find Q and Q′ in time O(ε -1/2C T+ε -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(ε -1/2C T). © 2005 Elsevier B.V.
Source Title: Computational Geometry: Theory and Applications
ISSN: 09257721
DOI: 10.1016/j.comgeo.2005.06.001
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 21, 2019


checked on Feb 12, 2019

Page view(s)

checked on Feb 9, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.