An O(n log n) algorithm for finding a shortest central link segment

Citation
Lg. Aleksandrov et al., An O(n log n) algorithm for finding a shortest central link segment, INT J C GEO, 10(2), 2000, pp. 157-188
Citations number
27
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
ISSN journal
02181959 → ACNP
Volume
10
Issue
2
Year of publication
2000
Pages
157 - 188
Database
ISI
SICI code
0218-1959(200004)10:2<157:AOLNAF>2.0.ZU;2-P
Abstract
A central link segment of a simple n-vertex polygon P is a segment s inside P that minimizes the quantity max(x epsilon P) min(y epsilon s) d(L)(x, y) , where d(L)(x, y) is the link distance between points a: and y of P. In th is paper we present an O(n log n) algorithm for finding a central link segm ent of P. This generalizes previous results for finding an edge or a segmen t of P from which P is visible. Moreover, in the same time bound, our algor ithm 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 minimu m value k for which a given polygon is k-visible from some segment.