Voronoi diagrams for direction-sensitive distances (communication)
O. Aichholzer, F. Aurenhammer, D. Chen, D. Lee, A. Mukhopadhyay, and
On a tilted plane
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
. Several optimal algorithms based on the
direction-sensitive distances on
are presented. For example, an
output-sensitive algorithm is developed for computing the skew distance
Voronoi diagram with
is the number of sites which have non-empty Voronoi regions
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
Reference: O. Aichholzer, F. Aurenhammer, D. Chen, D. Lee,
A. Mukhopadhyay, and E. Papadopoulou.
Voronoi diagrams for direction-sensitive distances (communication).
In Proc. Ann. ACM Symp. Computational Geometry, pages
418-420, Nice, France, 1997.
[SFB Report F003-098, TU Graz, Austria, 1996].