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

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 sites on , in time and
space, where is the number of sites which have non-empty Voronoi regions
(
). time and 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.