An almost distribution-independent incremental Delaunay triangulation algorithmZadravec, Mirko (Avtor) Žalik, Borut (Avtor) Delaunay triangulationincremental algorithmcomputational geometryskip listhash tableThis 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.20052012-06-01 09:41:43Neznano27042UDK: 004.92COBISS_ID: 9766422ISSN pri članku: 0178-2789NUK URN: URN:SI:UM:DK:XXVEGTFRsl