Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon

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

doi:10.1007/978-3-540-27798-9_29

Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon

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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

4 Scopus citations

Abstract

Given a convex polygon P with n vertices, we present algorithms to determine approximations of the largest axially symmetric convex polygon S contained in P, and the smallest such polygon S′ that contains P. More precisely, for any ε > 0, we can find an axially symmetric convex polygon Q ⊂ P with area |Q| > (1 - ε)|S| in time O(n + 1/ε^3/2), and we can find an axially symmetric convex polygon Q′ containing P with area |Q′| < (1 + ε)|S′| in time O(n+(1/ε²)log(1/ε)). If the vertices of P are given in a sorted array, we can obtain the same results in time O((1/√ε) log n+1/ε^3/2) and O((1/ε) log n+(1/ε²) log(1/ε)) respectively.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Kyung-Yong Chwa, J. Ian Munro
Publisher	Springer Verlag
Pages	259-267
Number of pages	9
ISBN (Electronic)	354022856X, 9783540228561
DOIs	https://doi.org/10.1007/978-3-540-27798-9_29
State	Published - 2004
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3106
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-27798-9_29

Cite this

Ahn, H. K., Brass, P., Cheong, O., Na, H. S., Shin, C. S., & Vigneron, A. (2004). Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon. In K-Y. Chwa, & J. Ian Munro (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 259-267). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3106). Springer Verlag. https://doi.org/10.1007/978-3-540-27798-9_29

Ahn, Hee Kap ; Brass, Peter ; Cheong, Otfried ; Na, Hyeon Suk ; Shin, Chan Su ; Vigneron, Antoine. / Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Kyung-Yong Chwa ; J. Ian Munro. Springer Verlag, 2004. pp. 259-267 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{afde742ecbc14e0c9c3b09948d077fd1,

title = "Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon",

abstract = "Given a convex polygon P with n vertices, we present algorithms to determine approximations of the largest axially symmetric convex polygon S contained in P, and the smallest such polygon S′ that contains P. More precisely, for any ε > 0, we can find an axially symmetric convex polygon Q ⊂ P with area |Q| > (1 - ε)|S| in time O(n + 1/ε3/2), and we can find an axially symmetric convex polygon Q′ containing P with area |Q′| < (1 + ε)|S′| in time O(n+(1/ε2)log(1/ε)). If the vertices of P are given in a sorted array, we can obtain the same results in time O((1/√ε) log n+1/ε3/2) and O((1/ε) log n+(1/ε2) log(1/ε)) respectively.",

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

year = "2004",

doi = "10.1007/978-3-540-27798-9_29",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "259--267",

editor = "Kyung-Yong Chwa and {Ian Munro}, J.",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Ahn, HK, Brass, P, Cheong, O, Na, HS, Shin, CS & Vigneron, A 2004, Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon. in K-Y Chwa & J Ian Munro (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3106, Springer Verlag, pp. 259-267. https://doi.org/10.1007/978-3-540-27798-9_29

Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon. / Ahn, Hee Kap; Brass, Peter; Cheong, Otfried; Na, Hyeon Suk; Shin, Chan Su; Vigneron, Antoine.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Kyung-Yong Chwa; J. Ian Munro. Springer Verlag, 2004. p. 259-267 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3106).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon

AU - Ahn, Hee Kap

AU - Brass, Peter

AU - Cheong, Otfried

AU - Na, Hyeon Suk

AU - Shin, Chan Su

AU - Vigneron, Antoine

PY - 2004

Y1 - 2004

N2 - Given a convex polygon P with n vertices, we present algorithms to determine approximations of the largest axially symmetric convex polygon S contained in P, and the smallest such polygon S′ that contains P. More precisely, for any ε > 0, we can find an axially symmetric convex polygon Q ⊂ P with area |Q| > (1 - ε)|S| in time O(n + 1/ε3/2), and we can find an axially symmetric convex polygon Q′ containing P with area |Q′| < (1 + ε)|S′| in time O(n+(1/ε2)log(1/ε)). If the vertices of P are given in a sorted array, we can obtain the same results in time O((1/√ε) log n+1/ε3/2) and O((1/ε) log n+(1/ε2) log(1/ε)) respectively.

AB - Given a convex polygon P with n vertices, we present algorithms to determine approximations of the largest axially symmetric convex polygon S contained in P, and the smallest such polygon S′ that contains P. More precisely, for any ε > 0, we can find an axially symmetric convex polygon Q ⊂ P with area |Q| > (1 - ε)|S| in time O(n + 1/ε3/2), and we can find an axially symmetric convex polygon Q′ containing P with area |Q′| < (1 + ε)|S′| in time O(n+(1/ε2)log(1/ε)). If the vertices of P are given in a sorted array, we can obtain the same results in time O((1/√ε) log n+1/ε3/2) and O((1/ε) log n+(1/ε2) log(1/ε)) respectively.

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

U2 - 10.1007/978-3-540-27798-9_29

DO - 10.1007/978-3-540-27798-9_29

M3 - Chapter

AN - SCOPUS:33244494885

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 259

EP - 267

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Chwa, Kyung-Yong

A2 - Ian Munro, J.

PB - Springer Verlag

ER -

Ahn HK, Brass P, Cheong O, Na HS, Shin CS, Vigneron A. Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon. In Chwa K-Y, Ian Munro J, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 259-267. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-27798-9_29

Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this