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

doi:10.1016/j.comgeo.2005.06.001

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 journal › Article › peer-review

19 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 language	English (US)
Pages (from-to)	152-164
Number of pages	13
Journal	Computational Geometry: Theory and Applications
Volume	33
Issue number	3
DOIs	https://doi.org/10.1016/j.comgeo.2005.06.001
State	Published - Feb 2006
Externally published	Yes

Bibliographical note

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: [email protected] (H.-K. Ahn), [email protected] (P. Brass), [email protected] (O. Cheong), [email protected] (H.-S. Na), [email protected] (C.-S. Shin), [email protected] (A. Vigneron).

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

Access to Document

10.1016/j.comgeo.2005.06.001

Cite this

@article{bce5378ab8b24a20b33155d87aba7201,

title = "Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets",

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

keywords = "Approximation, Axial symmetry, Shape matching",

author = "Ahn, {Hee Kap} and Peter Brass and Otfried Cheong and Na, {Hyeon Suk} and Shin, {Chan Su} and Antoine Vigneron",

note = "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: [email protected] (H.-K. Ahn), [email protected] (P. Brass), [email protected] (O. Cheong), [email protected] (H.-S. Na), [email protected] (C.-S. Shin), [email protected] (A. Vigneron).",

year = "2006",

month = feb,

doi = "10.1016/j.comgeo.2005.06.001",

language = "English (US)",

volume = "33",

pages = "152--164",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "3",

}

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: [email protected] (H.-K. Ahn), [email protected] (P. Brass), [email protected] (O. Cheong), [email protected] (H.-S. Na), [email protected] (C.-S. Shin), [email protected] (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 -

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

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this