Abstract
This paper studies the point location problem in Delaunay triangulations without preprocessing and additional storage. The proposed procedure finds the query point by simply "walking through" the triangulation, after selecting a "good starting point" by random sampling. The analysis generalizes and extends a recent result for d = 2 dimensions by proving this procedure takes expected time close to O(n1/(d+1)) for point location in Delaunay triangulations of n random points in d = 3 dimensions. Empirical results in both two and three dimensions show that this procedure is efficient in practice. © 1999 Elsevier Science B.V. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 63-83 |
| Journal | Computational Geometry: Theory and Applications |
| Volume | 12 |
| Issue number | 1-2 |
| DOIs | |
| Publication status | Published - Feb 1999 |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Research Keywords
- Computational geometry
- Delaunay triangulations
- Geometric computing
- Point location
- Randomized algorithms
- Three dimensional
Fingerprint
Dive into the research topics of 'Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver