We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
An O(n log n) Algorithm for Finding a Shortest Central Link Segment.
- Authors
Aleksandrov, Lyudmil G.; Djidjev, Hristo N.; Sack, Jörg-Rüdiger; Lee, D. T.
- Abstract
A central link segment of a simple n-vertex polygon P is a segment s inside P that minimizes the quantity max[sub x∈P] min[sub y∈s] d[sub L] (χ, y), where d[sub L] (χ, y) is the link distance between points x and y of P. In this paper we present an O(n log n) algorithm for finding a central link segment of P. This generalizes previous results for finding an edge or a segment of P from which P is visible. Moreover, in the same time bound, our algorithm finds a central link segment of minimum length. Constructing a central link segment has applications to the problems of finding an optimal robot placement in a simply connected polygonal region and determining the minimum value k for which a given polygon is k-visible from some segment.
- Subjects
ALGORITHMS; LINK theory; POLYGONS
- Publication
International Journal of Computational Geometry & Applications, 2000, Vol 10, Issue 2, p157
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195900000103