|
|||||
|
|
AnO(n logn) algorithm for computing the link center of a simple polygon |
|
| Authors: | Hristo N Djidjev Andrzej Lingas Jörg-Rüdiger Sack |
| Institution: | (1) Department of Computer Science, Rice University, P.O. Box 1892, 77251 Houston, TX, USA;(2) Department of Computer Science, Lund University, Box 118, S-22100 Lund, Sweden;(3) School of Computer Science, Carleton University, K1S 5B6 Ottawa, Ontario, Canada |
| Abstract: | We present an algorithm that determines the link center of a simplen-vertex polygonP inO(n logn) time. The link center of a simple polygon is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. The link distance between two pointsx andy insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx andy. Using our algorithm we also obtain anO(n logn)-time solution to the problem of determining the link radius ofP. The link radius ofP is the maximum link distance from a point in the link center to any vertex ofP. Both results are improvements over theO(n 2) bounds previously established for these problems. The research of J.-R. Sack was supported by the Natural Sciences and Engineering Research Council of Canada. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |