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: Contribution to journalArticlepeer-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/ε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.

Original languageEnglish (US)
Pages (from-to)259-267
Number of pages9
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3106
StatePublished - 2004
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon'. Together they form a unique fingerprint.

Cite this