Technical Report No. 31, July 1991 - Abstract

Bengt J. Nilsson, Sven Schuierer:
An Optimal Algorithm for the Rectilinear Link Center of a Rectilinear Polygon

Given a connected, undirected distance graph with required classes of nodes and optional Steiner nodes, find a shortest tree containing at least one node of each required class. This problem called Class Steiner Tree ist NP-hard and therefore we are dependent on approximation.

The problem of finding the link center of a simple polygon has been studied extensively in recent years. O(n*log n) time upper bounds have been given for this problem and that of computing the link diameter for the polygon.

We consider the rectilinear case of this problem and give linear time algorithms to compute the rectilinear link diamter and the rectilinear link center of a simple rectilinear polygon. As a consequence we also obtain a linear time solution for the rectilinear link radius problem. To our knowledge these are the first optimal algorithms for center and diameter problems of polygons.