External Incremental Delaunay Triangulation
Yifeng Cai · 2025
Read External Incremental Delaunay Triangulation by Yifeng Cai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-10786.txt.
Description
Yifeng Cai presents an external incremental method for Delaunay triangulation. His 2025 arXiv paper builds triangulations point by point from outside. Classic random incremental methods work with triangles as basic units. They must locate which triangle holds each new point. That search step complicates code and slows the build.
The new approach uses the convex hull and points as its basic units. Each added point lies outside the current hull by construction. No containment search is ever needed for a new point. Sorting points costs the standard log-linear time. Tangent searches across the whole build cost only linear time. Tests on uniform point sets showed linear total construction. Data structures, proofs, and comparisons fill out the paper.
Catalog record
| CREATOR | Yifeng Cai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-10786