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.