The Library
An O(n log n) algorithm for finding a shortest central link segment
Tools
UNSPECIFIED (2000) An O(n log n) algorithm for finding a shortest central link segment. INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 10 (2). pp. 157-188. ISSN 0218-1959.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | ||||
Publisher: | WORLD SCIENTIFIC PUBL CO PTE LTD | ||||
ISSN: | 0218-1959 | ||||
Official Date: | April 2000 | ||||
Dates: |
|
||||
Volume: | 10 | ||||
Number: | 2 | ||||
Number of Pages: | 32 | ||||
Page Range: | pp. 157-188 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |