Edge insertion for optimal triangulations

1993/07/01 by Marshall Bern, M. Bern, Herbert Edelsbrunner +6 · 35 citations
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #Computer science #Constrained Delaunay triangulation #Delaunay triangulation #Enhanced Data Rates for GSM Evolution #Geometry #Mathematical analysis #Mathematics #Minimum-weight triangulation #Piecewise #Piecewise linear function #Point (geometry) #Point set triangulation #Polynomial #Set (abstract data type) #Surface (topology) #Triangulation

paper · pdf · doi:10.1007/bf02573962

published in Discrete & Computational Geometry 10(1), 47-65 (Springer Science and Business Media LLC)

crossref issued 1993/07/01 · crossref published 1993/07/01 · crossref published-online 1993/07/01 · crossref published-print 1993/07/01 · openalex publication_date 1993/07/01 · crossref created 2007/03/22 · crossref deposited 2019/05/18 · openalex created_date 2025/10/10 · crossref indexed 2025/12/01 · openalex updated_date 2026/07/23

Citations

• An O(n² log n) Time Algorithm for the Minmax Angle Triangulation
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Randomized incremental construction of Delaunay and Voronoi diagrams
• A sweepline algorithm for Voronoi diagrams
• On triangulations of a set of points in the plane

Cited by

• The NP-completeness column
• On β-skeleton as a subgraph of the minimum weight triangulation
• Point-set triangulation [wikipedia]