TR-148: An O(N Log N) Algorithm for Computing a Link Center in a Simple Polygon

Abstract

We present an algorithm that determines, in O(n log n) time, the link center of a simple n­vertex polygon P. 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(n2) bounds previously established for these problems.