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

## IDA Technical Reports: abstract

*Generated: Thu, 24 Apr 2014 08:36:39 *

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>*