### Technical Report No. 55, June 1994 - Abstract

**Sven Schuierer:**

*An Optimal Data Structure for Shortest Rectilinear Path Queries in a Simple Rectilinear Polygon*

We present a data structure that allows to preprocess a rectilinear
polygon with *n* vertices such that, for any two query points, the
shortest path in the rectilinear link or *L1*-metric can be reported in
time *O(log n + k)* where *k* is the link length of the shortest
path. If only the distance is of interest, the query time reduces to
*O(log n)*. Furthermore, if the query points are two vertices, the
distance can be reported in time *O(1)* and a shortest path can be
constructed in time *O(1 + k)*. The data structure can be computed in
time *O(n)* and needs *O(n)* storage. As an application we present a
linear time algorithm to compute the diameter of a simple rectilinear
polygon with respect to the *L1*-metric.

report55.ps.gz