Computer Science – Computational Geometry
Scientific paper
1999-07-16
Computer Science
Computational Geometry
19 pages, 7 figures Proc. 14th Annu. ACM Sympos. Comput. Geom., 106--115, 1998
Scientific paper
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.
No associations
LandOfFree
Improved Incremental Randomized Delaunay Triangulation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved Incremental Randomized Delaunay Triangulation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Incremental Randomized Delaunay Triangulation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-162628