Published in

Proceedings of the fourteenth annual symposium on Computational geometry - SCG '98

DOI: 10.1145/276884.276896

Links

Tools

Export citation

Search in Google Scholar

Improved Incremental Randomized Delaunay Triangulation

Journal article published in 1998 by Thme Gnie Logiciel, Projet Prisme, Olivier Devillers ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

: We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, and small memory occupation. The location structure is organized into several levels. The lowest level just consists of the triangulation, then each level contains the triangulation of a small sample of the levels below. Point location is done by marching in a triangulation to determine the nearest neighbor of the query at that level, then the march restarts from that neighbor at the level below. Using a small sample (3 %) allows a small memory occupation; the march and the use of the nearest neighbor to change levels quickly locate the query. Key-words: computational geometry, geometric computing, randomized algorithms, Delaunay triangulation, dynamic algorithms. This work was partially supported by ESPRIT LTR 21957 (CGAL) Triangulation de Delaunay incr#mentale randomis#e : encore un pas en avant. R#sum# : No...