Universität zu Köln

Jünger, Michael, Kaibel, Volker and Thienel, Stefan (1994). Computing Delaunay-Triangulations in Manhatten and Maximum Metric. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zpr94-174.pdf Download (342kB) | Preview

Abstract

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.

Item Type:	Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Kaibel, Volker UNSPECIFIED UNSPECIFIED UNSPECIFIED Thienel, Stefan UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-546923
Date:	1994
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54692