ǂAn ǂalmost distribution-independent incremental Delaunay triangulation algorithm

Mirko Zadravec (Author), Borut Žalik (Author)

Abstract

This paper presents a new incremental insertion algorithm for constructing a Delaunay triangulation. Firstly, the nearest point is found in order to speed up the location of a triangle containing a currently inserted point. A hash table and 1-3 deterministic skip lists, combined with a walking strategy, are used for this task. The obtained algorithm is compared with the most popular Delaunay triangulation algorithms. The algorithm has the following attractive features: it is fast and practically independent of the distribution of input points, it is not memory demanding, and it is numerically stable and easy to implement.

Keywords

Delaunajeva triangulacija;inkrementalni algoritmi;računalniška grafika;Delaunay triangulation;incremental algorithm;computational geometry;skip list;hash table;

Data

Language:	English
Year of publishing:	2005
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	004.92
COBISS:	9766422
ISSN:	0178-2789
Views:	1771
Downloads:	88
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary keywords:	Delaunajeva triangulacija;inkrementalni algoritmi;računalniška grafika;
URN:	URN:SI:UM:
Pages:	str. 384-396
Volume:	ǂVol. ǂ21
Issue:	ǂNo. ǂ6
Chronology:	jul. 2005
ID:	8718311