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.