Skew Voronoi diagrams

On a tilted plane T in three-space, skew distances are defined as the Eucli dean distance plus a multiple of the signed difference in height. Skew dist ances may model realistic environments more closely than the Euclidean dist ance. Voronoi diagrams and related problems under this kind of distances ar e investigated. A relationship to convex distance functions and to Euclidea n Voronoi diagrams for planar circles is shown, and is exploited for a geom etric analysis and a plane-sweep construction of Voronoi diagrams on T. An output-sensitive algorithm running in time O(n log h) is developed, where n and h are the numbers of sites and non-empty Voronoi regions, respectively . The all nearest neighbors problem for skew distances, which has certain f eatures different from its Euclidean counterpart, is solved in O(n log n) t ime.