DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.40

Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface

Authors: Loïc Dubois

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

Every surface that is intrinsically polyhedral can be represented by a portalgon: a collection of polygons in the Euclidean plane with some pairs of equally long edges abstractly identified. While this representation is arguably simpler than meshes (flat polygons in ℝ³ forming a surface), it has unbounded happiness: a shortest path in the surface may visit the same polygon arbitrarily many times. This pathological behavior is an obstacle towards efficient algorithms. On the other hand, Löffler, Ophelders, Staals, and Silveira [SoCG 2023] recently proved that the (intrinsic) Delaunay triangulations have bounded happiness. In this paper, given a closed polyhedral surface S, represented by a triangular portalgon T, we provide an algorithm to compute the Delaunay triangulation of S whose vertices are the singularities of S (the points whose surrounding angle is distinct from 2π). The time complexity of our algorithm is polynomial in the number of triangles and in the logarithm of the aspect ratio r of T. Within our model of computation, we show that the dependency in log r is unavoidable. Our algorithm can be used to pre-process a triangular portalgon before computing shortest paths on its surface, and to determine whether the surfaces of two triangular portalgons are isometric.

Cite as

Loïc Dubois. Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dubois:LIPIcs.SoCG.2026.40,
  author =	{Dubois, Lo\"{i}c},
  title =	{{Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.40},
  URN =		{urn:nbn:de:0030-drops-258460},
  doi =		{10.4230/LIPIcs.SoCG.2026.40},
  annote =	{Keywords: Polyhedral surface, intrinsic Delaunay triangulation, algorithmic complexity}
}

Document

DOI: 10.4230/LIPIcs.ESA.2024.50

Making Multicurves Cross Minimally on Surfaces

Authors: Loïc Dubois

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

On an orientable surface S, consider a collection Γ of closed curves. The (geometric) intersection number i_S(Γ) is the minimum number of self-intersections that a collection Γ' can have, where Γ' results from a continuous deformation (homotopy) of Γ. We provide algorithms that compute i_S(Γ) and such a Γ', assuming that Γ is given by a collection of closed walks of length n in a graph M cellularly embedded on S, in O(n log n) time when M and S are fixed. The state of the art is a paper of Despré and Lazarus [SoCG 2017, J. ACM 2019], who compute i_S(Γ) in O(n²) time, and Γ' in O(n⁴) time if Γ is a single closed curve. Our result is more general since we can put an arbitrary number of closed curves in minimal position. Also, our algorithms are quasi-linear in n instead of quadratic and quartic. Most importantly, our proofs are simpler, shorter, and more structured. We use techniques from two-dimensional topology and from the theory of hyperbolic surfaces. Most notably, we prove a new property of the reducing triangulations introduced by Colin de Verdière, Despré, and Dubois [SODA 2024], reducing our problem to the case of surfaces with boundary. As a key subroutine, we rely on an algorithm of Fulek and Tóth [JCO 2020].

Cite as

Loïc Dubois. Making Multicurves Cross Minimally on Surfaces. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dubois:LIPIcs.ESA.2024.50,
  author =	{Dubois, Lo\"{i}c},
  title =	{{Making Multicurves Cross Minimally on Surfaces}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.50},
  URN =		{urn:nbn:de:0030-drops-211216},
  doi =		{10.4230/LIPIcs.ESA.2024.50},
  annote =	{Keywords: Algorithms, Topology, Surfaces, Closed Curves, Geometric Intersection Number}
}

Search Results

Documents authored by Dubois, Loïc

Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface

Abstract

Cite as

Making Multicurves Cross Minimally on Surfaces

Abstract

Cite as

Thanks for your feedback!

Could not send message