Skip to main content

An incremental construction algorithm for Delaunay triangulation using the nearest-point paradigm

Buy Article:

$60.90 plus tax (Refund Policy)


This paper introduces a new algorithm for constructing a 2D Delaunay triangulation. It belongs to the class of incremental insertion algorithms, which are known as less demanding from the implementation point of view. The most time consuming step of the incremental insertion algorithms is locating the triangle containing the next point to be inserted. In this paper, this task is transformed to the nearest point problem, which is solved by a two-level uniform subdivision acceleration technique. Dependencies on the distribution of the input points are reduced using this technique. The algorithm is compared with other popular triangulation algorithms: two variants of Guibas, Knuth, and Sharir's incremental insertion algorithm, two different implementations of Mücke's algorithm, Fortune's sweep-line algorithm, and Lee and Schachter's divide and conquer algorithm. The following point distributions are used for tests: uniform, regular, Gaussian, points arranged in clusters, and real data sets from a GIS database. Among all tested algorithms, the divide and conquer approach turns out to be the best. The proposed algorithm is the second fastest except for input points with highly non-uniform distribution. As implementation of the algorithm is simple, it represents an attractive alternative to other Delaunay triangulation algorithms used in practice.

Document Type: Research Article


Affiliations: 1: University of Maribor, Faculty of Electrical Engineering & Computer Sciences, Department of Computer Science, Maribor, Slovenia; e-mail: 2: University of West Bohemia, Faculty of Applied Sciences, Department of Computer Science and Engineering, Plzen, Czech Republic

Publication date: March 1, 2003

More about this publication?

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more