Computing correct Delaunay triangulations

Jünger, Michael and Reinelt, Gerhard and Zepf, Doris (1991) Computing correct Delaunay triangulations.
Published in: Computing : archives for informatics and numerical computation Vol. 47 (1). pp. 43-49.


In recent years the practical computation of Delaunay triangulations resp. Voronoi diagrams has received a lot of attention in the literature. While the Delaunay triangulation is an important basic tool in geometric optimization algorithms, it is nontrivial to achieve a numerically stable computer implementation. In this technical note we assume that all generating points are grid points of a regular M by M lattice in the plane. Depending on M we derive the necessary word length a binary computer must have for integer representation in order to obtain exact Delaunay triangulations. This analysis is carried out for the L1-, L2- and L-infinity-metric.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr90-096
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 24 Oct 2011 09:17