### Technical Report No. 49, February 1994 - Abstract

**Sven Schuierer:**

*An Optimal Algorithm for the Geodesic L1-Diameter and Center of a Simple Polygon*

The diameter of a set *S* of points is the maximal distance between a pair
of points in *S*. The center of *S* is the set of points that
minimize the
distance to their furthest neighbours. The problem of finding the diameter
and center of a simple polygon for different distance measures has been
studied extensively in recent years. *O(n*log n)* algorithms have been
given if the geodesic Euclidean or the link metric is used.

In this paper we consider the geodesic rectilinear case of this problem and
give linear time algorithms to compute the *L1* -diameter and the
*L1*-center of a simple rectilinear polygon which yields as a
consequence a linear time solution for the geodesic *L1*-radius problem.

report49.ps.gz