Skip to main content

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

Buy Article:

$55.00 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.
No Reference information available - sign in for access.
No Citation information available - sign in for access.
No Supplementary Data.
No Article Media
No Metrics

Document Type: Research Article

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

Publication date: 01 March 2003

More about this publication?
  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
X
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