APPROXIMATION ALGORITHMS FOR INSCRIBING OR CIRCUMSCRIBING AN AXIALLY SYMMETRIC POLYGON TO A CONVEX POLYGON
SCIE
SCOPUS
- Title
- APPROXIMATION ALGORITHMS FOR INSCRIBING OR CIRCUMSCRIBING AN AXIALLY SYMMETRIC POLYGON TO A CONVEX POLYGON
- Authors
- Ahn, HK; Brass, P; Cheong, O; Na, HS; Shin, CS; Vigneron, A
- Date Issued
- 2004-08
- Publisher
- SPRINGER-VERLAG BERLIN
- 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 e > 0, we can find an axially symmetric convex polygon Q c P with area \Q\ > (1 - epsilon)\S\ in time O(n + 1/epsilon(3/2)), and we can find an axially symmetric convex polygon Q' containing P with area \Q'\ < (1 + E)\S'\ in time 0(n + (1/epsilon(2)) log(1/epsilon)). If the vertices of P are given in a sorted array, we can obtain the same results in time O((1/rootepsilon) log n+1/epsilon(3/2)) and O((1/epsilon) log n+ (1/epsilon(2)) log(1/epsilon)) respectively.
- Keywords
- RECTANGLES; BODIES
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/28562
- ISSN
- 0302-9743
- Article Type
- Article
- Citation
- LECTURE NOTES IN COMPUTER SCIENCE, vol. 3106, page. 259 - 267, 2004-08
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.