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.