IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Tue, 23 Dec 2014 03:16:20

Djidjev, H. N., Lingas, A., and Sack, J.-R. (1989). An O(n log n) Algorithm for Computing a Link Center in a Simple Polygon. Technical Report LiTH-IDA-R-89-09, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the 6th Symposium on Theoretical Aspects of Computer Science, Paderborn, Germany, February 1989. (bibtex),

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.


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>