Voronoi diagrams for direction-sensitive distances (communication)

O. Aichholzer, F. Aurenhammer, D. Chen, D. Lee, A. Mukhopadhyay, and E. Papadopoulou

Abstract:

On a tilted plane $T$ in three-space, direction-sensitive distances are defined as the Euclidean distance plus a multiple of the signed difference in height. These direction-sensitive distances, called skew distances generalize the Euclidean distance and may model realistic environments more closely than the Euclidean distance. Various Voronoi diagrams and related problems under this kind of distances are investigated. A relationship to convex distance functions and to Euclidean Voronoi diagrams for planar circles is shown, and is exploited for a geometric analysis and a plane-sweep construction of Voronoi diagrams on $T$. Several optimal algorithms based on the direction-sensitive distances on $T$ are presented. For example, an output-sensitive algorithm is developed for computing the skew distance Voronoi diagram with $n$ sites on $T$, in $O(n \log h)$ time and $O(n)$ space, where $h$ is the number of sites which have non-empty Voronoi regions ( $1 \leq h \leq n$). $O(n \log n)$ time and $O(n)$ space algorithms are also given for several other problems under skew distances, including the all nearest neighbors and the layers of Voronoi diagram. These algorithms have certain features different from their 'ordinary' counterparts based on the Euclidean distance.

Reference: O. Aichholzer, F. Aurenhammer, D. Chen, D. Lee, A. Mukhopadhyay, and E. Papadopoulou. Voronoi diagrams for direction-sensitive distances (communication). In Proc. $13^{th}$ Ann. ACM Symp. Computational Geometry, pages 418-420, Nice, France, 1997. [SFB Report F003-098, TU Graz, Austria, 1996].