TY - JOUR

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

AU - Ahn, Hee Kap

AU - Brass, Peter

AU - Cheong, Otfried

AU - Na, Hyeon Suk

AU - Shin, Chan Su

AU - Vigneron, Antoine

N1 - Funding Information:
✩ This research was supported by the Brain Korea 21 Project, The School of Information Technology, KAIST, 2005; by the Soongsil University research fund; by the Hankuk University of Foreign Studies Research Fund of 2005; and by the National University of Singapore under grant R.252.000.166.112. * Corresponding author. E-mail addresses: heekap@gmail.com (H.-K. Ahn), peter@cs.ccny.cuny.edu (P. Brass), otfried@cs.kaist.ac.kr (O. Cheong), hsnaa@computing.ssu.ac.kr (H.-S. Na), cssin@hufs.ac.kr (C.-S. Shin), antoine@comp.nus.edu.sg (A. Vigneron).

PY - 2006/2

Y1 - 2006/2

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

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

KW - Approximation

KW - Axial symmetry

KW - Shape matching

UR - http://www.scopus.com/inward/record.url?scp=84867925351&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2005.06.001

DO - 10.1016/j.comgeo.2005.06.001

M3 - Article

AN - SCOPUS:84867925351

SN - 0925-7721

VL - 33

SP - 152

EP - 164

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 3

ER -