Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.comgeo.2005.06.001
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
Source: 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
URI: http://scholarbank.nus.edu.sg/handle/10635/39871
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.

SCOPUSTM   
Citations

13
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

10
checked on Dec 11, 2017

Page view(s)

57
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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