O. Aichholzer, F. Aurenhammer, D. Chen, D. Lee, and E. Papadopoulou
On a tilted plane
in three-space,
skew distances are defined as the
Euclidean distance plus a multiple of the signed difference in height. Skew
distances may model realistic environments more closely than the Euclidean
distance. 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
. An output-sensitive algorithm running in time
is
developed, where
and
is the number of sites and non-empty Voronoi
regions, respectively. The all nearest neighbors problem for skew distances,
which has certain features different from its Euclidean counterpart, is
solved in
time.