### 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.

report31.ps.gz