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 L 1 -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 w.r.t. the L 1 -metric.
The preprocessing time and space were both reduced to O(n) by Schuierer REF (with O(log n) query time).
An Optimal Data Structure for Shortest Rectilinear Path Queries in a Simple Rectilinear Polygon
Internat. J. Comput. Geom. Appl
Computer Science Mathematics