Authors: alik B.¹; Kolingerová I.²

Source: International Journal of Geographical Information Science, Volume 17, Number 2, 1 March 2003 , pp. 119-138(20)

Publisher: Taylor and Francis Ltd

Abstract:

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: zalik@uni-mb.si 2: University of West Bohemia, Faculty of Applied Sciences, Department of Computer Science and Engineering, Plzen, Czech Republic

Publication date: 2003-03-01

More about this publication?

• Editorial Board
• Information for Authors
• Subscribe to this Title
• ingentaconnect is not responsible for the content or availability of external websites

Related content

• In this: publication
• By this: publisher
• In this Subject: Geography
• By this author: alik B. ;  Kolingerová I.

Website © Publishing Technology. Article copyright remains with the publisher, society or author(s) as specified within the article.

• Terms and conditions
• Privacy policy
• Information for advertisers