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

CREATORYifeng Cai
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-10786

Browse the full library · About the Tower of Babel