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|
|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. https://doi.org/10.1016/j.comgeo.2005.06.001|
|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|
|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
WEB OF SCIENCETM
checked on Feb 12, 2019
checked on Feb 9, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.