Please use this identifier to cite or link to this item:
|Title:||Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon|
|Source:||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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3106 : 259-267. ScholarBank@NUS Repository.|
|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. © Springer-Verlag Berlin Heidelberg 2004.|
|Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jan 14, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.