Title: Skew Voronoi Diagram*

*Part of this work was carried out when the authors were visiting the Center for
Applied Science and Engineering and the Institute of Information Science, Academia Sinica, 
Nankang, Taiwan, June -- July 1996.


Oswin Aichholzer** and Franz Aurenhammer

Institute for Theoretical Computer Science
Graz University of Technology, Graz, Austria
e-mail: {oaich,auren}@igi.tu-graz.ac.at

**The research of this author was supported by the Austrian Spezialforschungsbereich F003, 
Optimierung und Kontrolle.

Danny Z. Chen#

Department of Computer Science & Engineering 
University of Notre Dame, Notre Dame, IN 46556
e-mail: chen@cse.nd.edu.

#Research supported in part by the National Science Foundation under Grant CCR-9623585.

D. T. Lee$

Department of Electrical and Computer Engineering,
Northwestern University,  Evanston, IL 60208,
e-mail: dtlee@ece.nwu.edu.

$Research supported in part by the National Science Foundation under the Grant CCR-9731638, 
and by the Office of Naval Research under the Grants No.~N00014-97-0514 and
No.~N00014-95-1-1007.

Evanthia Papadopoulou

IBM Watson Research Center
Yorktown Heights, NY 10598
e-mail: evanthia@watson.ibm.com

Abstract:

On a tilted plane $T$ 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. 
Voro-noi 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.
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 features different from its 
Euclidean counterpart, is solved in O(n log n) time.

Keywords: Direction-dependent distance, Voronoi diagram, additive weights, 
output-sensitive algorithm

Int'l J. Computational Geometry & Applications, 9(3):235-247, June 1999.