Computing delaunay triangulations in Manhattan and Maximum metric

We modify the incremental algorithm for computing Voronoi diagrams in the Euclidean metric proposed by Ohya, Iri and Murota [6] in order to obtain an algorithm for computing Voronoi diagrams (resp. Delaunay triangulations) in Manhattan and Maximum metric, that is rather simply to implement. We generalize the notions of 'Voronoi diagram' and 'Delaunay triangulation' in such a way that these structures still can be computed by an algorithm very similar to the one of Ohya, Iri and Murota, and that they contain - as special cases - analogons to the Euclidean Voronoi diagram (Delaunay triangulation) in the Manhattan and maximum metric. In this paper, we give a detailed description of the algorithm, that makes it (rather) easy to write a computer program that computes Delaunay triangulations for Manhattan or Maximum metric. (orig.)Available from TIB Hannover: RO 3476(174) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman