Loading...
Please wait, while we are loading the content...
Similar Documents
Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets
| Content Provider | CiteSeerX |
|---|---|
| Author | Ahn, Hee-Kap Brass, Peter Cheong, Otfried Na, Hyeon-Suk Shin, Chan-Su Vigneron, Antoine |
| 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 P, and the smallest such set S ′ that contains P. 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 TC: 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 TC = O(log n). Then we can find Q in time O(TCε −1/2 + ε −3/2) and we can find Q ′ in time O(TCε −1/2 + ε −3/2 log(ε −1)). Using these techniques, we can also find approximations to the perimeter, area, diameter, width, smallest enclosing restangle and smallest enclosing circle of C in time O(TCε −1/2). 1 |
| File Format | |
| Journal | Comput. Geom. Theory Appl |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Planar Convex Set Symmetric Polygon Approximation Algorithm Symmetric Convex Polygon Planar Convex Sublinear Approximation Algorithm Data Structure Extreme Point Symmetric Convex Sorted Array Time Tc Convex N-gon |
| Content Type | Text |
| Resource Type | Article |
