Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface

Loïc Dubois · 2026

Read Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface by Loïc Dubois (2026) 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-2601-03954.txt.

Introduction

Loïc Dubois, writing alone, gives an algorithm for computing the intrinsic Delaunay triangulation of a closed polyhedral surface. Surfaces can be shown as portalgons, flat polygon sets with edges glued in the abstract. That is simpler than 3D meshes but has a flaw called unbounded happiness: a shortest path may revisit one polygon endlessly. Delaunay triangulations were lately shown to avoid that flaw, making them the right frame for surface algorithms.

Given the surface as a triangular portalgon, the method computes the triangulation whose vertices are the surface's singularities, the points whose angle around them differs from a full turn. Its running time is polynomial in the triangle count and in the log of the aspect ratio. Fast intrinsic triangulations support geometry work on surfaces exactly as given, without embedding tricks.

Catalog record

CREATORLoïc Dubois
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE162 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-03954

Browse the full library · About the Tower of Babel