Computing Delaunay-Triangulations in Manhatten and Maximum Metric

Jünger, Michael and Kaibel, Volker and Thienel, Stefan (1994) Computing Delaunay-Triangulations in Manhatten and Maximum Metric.
Technical Report , 27 p.


Delaunay-Triangulations (the duals of Voronoi Diagrams) are well known to be structures that contain a lot of neighborhood-information about a given (finite) set of points in the plane. Many algorithms rely on efficient procedures to compute them in practical applications, yet the textbook descriptions usually only treat the case of Euclidean metric. We modify one of the algorithms known for the Euclidean case (the incremental algorithm of Ohya, Iri, and Murota) to become suitable for a more general class of ''Delaunay Triangulations'' including those for the Manhattan and Maximum metrics. We give a detailed description of this algorithm that makes it (rather) easy to write a computer program for the calculation of Delaunay Triangulations for these metrics. We give computational results for our own implementation of the algorithm.

Download: [img] Postscript
Download (539kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: No citation data.
Uncontrolled Keywords: Delaunay triangulation Manhattan metric Maximum metric Voronoi diagram
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Related URLs:
Deposit Information:
ZAIK Number: zpr94-174
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:21