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

Hee Kap Ahn*, Peter Brass, Otfried Cheong, Hyeon Suk Na, Chan Su Shin, Antoine Vigneron

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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).

Original languageEnglish (US)
Pages (from-to)152-164
Number of pages13
JournalComputational Geometry: Theory and Applications
Volume33
Issue number3
DOIs
StatePublished - Feb 1 2006

Keywords

  • Approximation
  • Axial symmetry
  • Shape matching

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets'. Together they form a unique fingerprint.

Cite this