@techreport{R-89-09,
TITLE = {An O(n log n) Algorithm for Computing a Link Center in a Simple Polygon},
AUTHOR = {Hristo N. Djidjev and Andrzej Lingas and J{\"o}rg-R. Sack },
YEAR = {1989},
NUMBER = {R-89-09},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-89-09+abstr},
ABSTRACT = {The problem of finding the link center of a simple n-vertex polygon P had previously been solved in quadratic time. It was posed as an open problem as to whether a faster algorithm exists for determining at least one point inside the link center. Here this question is answered affirmatively. We present an algorithm that determines, in O(n log n) time, either a triangle inside the link center or the entire link center. As a consequence, we also obtain an O(n log n) time solution to the problem of determining the link radius of P. Both results are improvements over the O(n**2) bound previously established.},
IDANR = {LiTH-IDA-R-89-09},
NOTE = {Also in Proc. of the 6th Symposium on Theoretical Aspects of Computer Science, Paderborn, Germany, February 1989}