caa a22 4500 469075112 CHVBK 20180323132933.0 cr unu---uuuuu 170328e19920801xx s 000 0 eng 10.1007/BF02293040 doi (NATIONALLICENCE)springer-10.1007/BF02293040 An O ( n log n ) algorithm for computing the link center of a simple polygon [Elektronische Daten] [Hristo Djidjev, Andrzej Lingas, Jörg-Rüdiger Sack] 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. Springer-Verlag New York Inc., 1992 Djidjev Hristo Department of Computer Science, Rice University, P.O. Box 1892, 77251, Houston, TX, USA aut Lingas Andrzej Department of Computer Science, Lund University, Box 118, S-22100, Lund, Sweden aut Sack Jörg-Rüdiger School of Computer Science, Carleton University, K1S 5B6, Ottawa, Ontario, Canada aut Discrete & Computational Geometry Springer New York 8/2(1992-08-01), 131-152 0179-5376 8:2<131 1992 8 454 https://doi.org/10.1007/BF02293040 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293040 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Djidjev Hristo Department of Computer Science, Rice University, P.O. Box 1892, 77251, Houston, TX, USA aut NATIONALLICENCE 700 1- Lingas Andrzej Department of Computer Science, Lund University, Box 118, S-22100, Lund, Sweden aut NATIONALLICENCE 700 1- Sack Jörg-Rüdiger School of Computer Science, Carleton University, K1S 5B6, Ottawa, Ontario, Canada aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/2(1992-08-01), 131-152 0179-5376 8:2<131 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer