34 Search Results for "Boissonnat, Jean-Daniel"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.37
A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach

Authors: Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken

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

Abstract
Assumptions on the reach are crucial for ensuring the correctness of many geometric and topological algorithms, including triangulation, manifold reconstruction and learning, homotopy reconstruction, and methods for estimating curvature or reach. However, these assumptions are often coupled with the requirement that the manifold be smooth, typically at least C². In this paper, we prove that any manifold with positive reach can be approximated arbitrarily well by a C^∞ manifold without significantly reducing the reach. More precisely, given a manifold with reach R, we construct a manifold that is ε-close to it in the C¹ sense (both the manifold and its tangent spaces are close), and has reach at least R-ε. The proof employs techniques from differential topology - partitions of unity and smoothing using convolution kernels. This result implies that nearly all theorems established for C² or manifolds with a certain reach naturally extend to manifolds with the same reach, even if they are not C², for free!
Cite as

Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken. A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dalpozkourimska_et_al:LIPIcs.SoCG.2026.37,
  author =	{Dal Poz Kou\v{r}imsk\'{a}, Hana and Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{37:1--37:19},
  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.37},
  URN =		{urn:nbn:de:0030-drops-258434},
  doi =		{10.4230/LIPIcs.SoCG.2026.37},
  annote =	{Keywords: Reach, Manifolds, Smoothing, Differentiability, Differential topology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.42
Compressed Data Structures for Heegaard Splitting

Authors: Henrique Ennes and Clément Maria

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

Abstract
Heegaard splittings provide a natural representation of closed 3-manifolds by gluing handlebodies along a common surface. These splittings can be equivalently given by two finite sets of meridians lying on the surface, which define a Heegaard diagram. We present a data structure to effectively represent Heegaard diagrams as normal curves with respect to triangulations of a surface of complexity measured by the space required to express the normal coordinates' vectors in binary. This structure can be significantly more compressed than triangulations of 3-manifolds, giving exponential gains for some families. Even with this succinct definition of complexity, we establish polynomial-time algorithms for comparing and manipulating diagrams, performing stabilizations, detecting trivial stabilizations and reductions, and computing topological invariants of the underlying manifolds, such as their fundamental and homology groups. We also contrast early implementations of our techniques with standard software programs for 3-manifolds, achieving faster algorithms for the average cases and exponential gains in speed for some particular presentations of the inputs.
Cite as

Henrique Ennes and Clément Maria. Compressed Data Structures for Heegaard Splitting. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ennes_et_al:LIPIcs.SoCG.2026.42,
  author =	{Ennes, Henrique and Maria, Cl\'{e}ment},
  title =	{{Compressed Data Structures for Heegaard Splitting}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{42:1--42: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.42},
  URN =		{urn:nbn:de:0030-drops-258484},
  doi =		{10.4230/LIPIcs.SoCG.2026.42},
  annote =	{Keywords: 3-manifold, Heegaard splitting, curves on surfaces, surface theory, data structure, computational topology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.45
Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications

Authors: Sándor P. Fekete, Prahlad Narasimhan Kasthurirangan, Phillip Keldenich, Fabian Kollhoff, Chek-Manh Loi, and Michael Perk

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

Abstract
The weak visibility polygon of a line segment s inside a simple polygon P, denoted by V_P(s), is the region of the polygon that is visible from at least one point on s. Given its fundamental nature in computational geometry, several algorithms have been proposed to compute weak visibility polygons efficiently, each with different trade-offs in terms of preprocessing time, query time, and space complexity. Although there are many applications that require computing these polygons such as computer graphics, robot motion planning, and network communication systems, there is a lack of any implementations of these algorithms in the literature - not to mention one that is exact, robust, and scalable. Furthermore, weak segment visibility polygons are used as basic building blocks in several other algorithms, such as in minimum-link path computation. In this work, we present an implementation of an optimal linear-time algorithm for computing the weak visibility polygon of a segment inside a triangulated simple polygon. Our implementation provides exact, robust geometric primitives and optimizations to handle large inputs with more than 18,000,000 vertices. We demonstrate two concrete applications: (1) construction of window partitions, a standard data structure in visibility algorithms, and (2) support for optimal minimum-link path queries between two points in a simple polygon, the latter serving as a direct use case of the former. Experimental results on a variety of polygon families confirm that the end-to-end running time scales linearly with the size of the polygon and is dominated by the cost of computing the triangulation, validating the practicality and scalability of the approach. The implementation is released as open source in the format of a CGAL package to support reproducibility and further research.
Cite as

Sándor P. Fekete, Prahlad Narasimhan Kasthurirangan, Phillip Keldenich, Fabian Kollhoff, Chek-Manh Loi, and Michael Perk. Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.45,
  author =	{Fekete, S\'{a}ndor P. and Kasthurirangan, Prahlad Narasimhan and Keldenich, Phillip and Kollhoff, Fabian and Loi, Chek-Manh and Perk, Michael},
  title =	{{Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{45:1--45:19},
  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.45},
  URN =		{urn:nbn:de:0030-drops-258516},
  doi =		{10.4230/LIPIcs.SoCG.2026.45},
  annote =	{Keywords: Visibility, line segments, link distance, window partition, computation, implementation, robustness, scalability, exactness, CGAL}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.60
Space-Efficient Approximate Spherical Range Counting in High Dimensions

Authors: Andreas Kalavas and Ioannis Psarros

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

Abstract
We study the following range searching problem in high-dimensional Euclidean spaces: given a finite set P ⊂ ℝ^d, where each p ∈ P is assigned a weight w_p, and radius r > 0, we need to preprocess P into a data structure such that when a new query point q ∈ ℝ^d arrives, the data structure reports the cumulative weight of points of P within Euclidean distance r from q. Solving the problem exactly seems to require space usage that is exponential to the dimension, a phenomenon known as the curse of dimensionality. Thus, we focus on approximate solutions where points up to (1+ε)r away from q may be taken into account, where ε > 0 is an input parameter known during preprocessing. We build a data structure with near-linear space usage, and query time in n^{1-Θ(ε⁴/log(1/ε))}+t_q^ϱ⋅n^{1-ϱ}, for some ϱ = Θ(ε²), where t_q is the number of points of P in the ambiguity zone, i.e., at distance between r and (1+ε)r from the query q. To the best of our knowledge, this is the first data structure with efficient space usage (subquadratic or near-linear for any ε > 0) and query time that remains sublinear for any sublinear t_q. We supplement our worst-case bounds with a query-driven preprocessing algorithm to build data structures that are well-adapted to the query distribution.
Cite as

Andreas Kalavas and Ioannis Psarros. Space-Efficient Approximate Spherical Range Counting in High Dimensions. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kalavas_et_al:LIPIcs.SoCG.2026.60,
  author =	{Kalavas, Andreas and Psarros, Ioannis},
  title =	{{Space-Efficient Approximate Spherical Range Counting in High Dimensions}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{60:1--60: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.60},
  URN =		{urn:nbn:de:0030-drops-258670},
  doi =		{10.4230/LIPIcs.SoCG.2026.60},
  annote =	{Keywords: Approximate range counting, partition trees, high dimensions}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.74
Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach

Authors: André Lieutier and Mathijs Wintraecken

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

Abstract
This paper contains three main results. Firstly, we give an elementary proof of the following statement: Let ℳ be a topological manifold without boundary embedded in R^d. If ℳ has positive reach, then ℳ can locally be written as the graph of a C^{1,1} function from the tangent space to the normal space. Conversely if ℳ can locally be written as the graph of a C^{1,1} function from the tangent space to the normal space, then ℳ has positive reach. The result was hinted at by Federer when he introduced the reach, and proved by Lytchak. Lytchak’s proof relies heavily on CAT(k)-theory. The proof presented here uses only basic results on homology. Secondly, we give optimal Lipschitz-constants for the derivative, in other words we give an optimal bound for the angle between tangent spaces in term of the distance between the points. We stress that Lytchak did not provide any bound, let alone an optimal one, making his proof, although interesting from a mathematical perspective, ineffectual in an algorithmic setting. To provide precise and optimal bounds on the angle between tangent spaces, we formally introduce the local reach for sets of positive reach, based on Aamari et al.’s discussion for C² manifolds. We prove that the local reach of a manifold is completely characterized by the variation of tangent spaces. This improves earlier results, that were either suboptimal or assumed that the manifold was C². Thirdly, we show that the value of the reach is equals minimum of the local reach of the set and a global bottleneck for any set. This generalizes a result by Aamari et al. which explains how the reach is attained for C² manifolds.
Cite as

André Lieutier and Mathijs Wintraecken. Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 74:1-74:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lieutier_et_al:LIPIcs.SoCG.2026.74,
  author =	{Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{74:1--74:16},
  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.74},
  URN =		{urn:nbn:de:0030-drops-258812},
  doi =		{10.4230/LIPIcs.SoCG.2026.74},
  annote =	{Keywords: Reach, Manifolds, Differentiability class, Lipschitz continuity, Tangent space}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.75
Geodesics of Length Less Than πR in a Set of Reach R Are Unique and Continuous with Respect to the Endpoints

Authors: André Lieutier and Mathijs Wintraecken

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

Abstract
Positive reach underpins many results in computational geometry and topology. It is used for triangulation criteria, topological inference, and manifold learning. The geometric properties of these sets have therefore been studied intensely. Here we focus on the shortest paths or minimizing geodesics in these sets. Our main result states that minimizing geodesics of length strictly less than π R in a set of reach R are unique. This in turn implies that such minimizing geodesics are continuous with respect to the endpoints.
Cite as

André Lieutier and Mathijs Wintraecken. Geodesics of Length Less Than πR in a Set of Reach R Are Unique and Continuous with Respect to the Endpoints. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 75:1-75:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lieutier_et_al:LIPIcs.SoCG.2026.75,
  author =	{Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{Geodesics of Length Less Than \piR in a Set of Reach R Are Unique and Continuous with Respect to the Endpoints}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{75:1--75:12},
  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.75},
  URN =		{urn:nbn:de:0030-drops-258823},
  doi =		{10.4230/LIPIcs.SoCG.2026.75},
  annote =	{Keywords: Reach, geodesics, metric geometry}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.84
The Voronoi Diagram of Four Lines in ℝ³

Authors: Evanthia Papadopoulou and Zeyu Wang

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

Abstract
We consider the Voronoi diagram of lines in ℝ³ under the Euclidean metric, and give a full classification of its structure in the base case of four lines in general position. We first show that the number of vertices in the Voronoi diagram of four lines in general position is always even, between 0 and 8, and all such numbers can be realized. We identify a key structure for the diagram formation, called a twist, which is a pair of consecutive intersections among trisector branches; only two types of twists are possible, so-called full and partial twists. A full twist is a purely local structure, which can be inserted or removed without affecting the rest of the diagram. Assuming no full twists, the nearest and the farthest Voronoi diagrams of four lines, each have 15 distinct topologies, which are in one-to-one correspondence; the two-dimensional faces are all unbounded, and the total number of vertices is at most six. The unbounded features of the farthest diagram, encoded in a two-dimensional spherical map, are also in one-to-one correspondence. The identified topologies are all realizable. Any Voronoi diagram of four lines in general position in ℝ³ can be obtained from one of these topologies by inserting full twists; each twist induces a bounded face of exactly two vertices in both the nearest and farthest diagrams. We obtain the classification by an exhaustive search algorithm using some new structural and combinatorial observations of line Voronoi diagrams.
Cite as

Evanthia Papadopoulou and Zeyu Wang. The Voronoi Diagram of Four Lines in ℝ³. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 84:1-84:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{papadopoulou_et_al:LIPIcs.SoCG.2026.84,
  author =	{Papadopoulou, Evanthia and Wang, Zeyu},
  title =	{{The Voronoi Diagram of Four Lines in \mathbb{R}³}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{84:1--84:17},
  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.84},
  URN =		{urn:nbn:de:0030-drops-258916},
  doi =		{10.4230/LIPIcs.SoCG.2026.84},
  annote =	{Keywords: Voronoi diagram, lines, three dimensions, structural properties}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.90
Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells

Authors: Jonathan Richard Shewchuk

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

Abstract
The restricted Delaunay triangulation of a closed surface Σ and a finite point set V ⊂ Σ is a subcomplex of the Delaunay tetrahedralization of V whose triangles approximate Σ. It is well known that if V is a sufficiently dense sample of a smooth Σ, then the union of the restricted Delaunay triangles is homeomorphic to Σ. We show that an ε-sample with ε ≤ 0.3245 suffices. By comparison, Dey proves it for a 0.18-sample; our improved sampling bound reduces the number of sample points required by a factor of 3.25. More importantly, we improve a related sampling bound of Cheng et al. for Delaunay surface meshing, reducing the number of sample points required by a factor of 21. The first step of our homeomorphism proof is particularly interesting: we show that for a 0.44-sample, the restricted Voronoi cell of each site v ∈ V is homeomorphic to a disk, and the orthogonal projection of the cell onto T_vΣ (the plane tangent to Σ at v) is star-shaped.
Cite as

Jonathan Richard Shewchuk. Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 90:1-90:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shewchuk:LIPIcs.SoCG.2026.90,
  author =	{Shewchuk, Jonathan Richard},
  title =	{{Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{90:1--90:16},
  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.90},
  URN =		{urn:nbn:de:0030-drops-258961},
  doi =		{10.4230/LIPIcs.SoCG.2026.90},
  annote =	{Keywords: Restricted Delaunay triangulation, restricted Voronoi diagram, surface sampling, surface mesh generation, surface reconstruction, \epsilon-sample, homeomorphism}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.92
Estimation of Conformal Metrics

Authors: Jérôme Taupin

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

Abstract
We study deformations of the geodesic distances on a domain of ℝ^N induced by a function called conformal factor. We show that under a positive reach assumption on the domain (not necessarily a submanifold) and mild assumptions on the conformal factor, geodesics for the conformal metric have good regularity properties in the form of a lower bounded reach. This regularity allows for efficient estimation of the conformal metric from a random point cloud with a relative error proportional to the Hausdorff distance between the point cloud and the original domain. We then establish convergence rates of order n^{-1/d} that are close to sharp when the intrinsic dimension d of the domain is large, for an estimator that can be computed in O(n²) time. Finally, this paper includes a useful equivalence result between ball graphs and nearest-neighbors graphs when assuming Ahlfors regularity of the sampling measure, allowing to transpose results from one setting to another.
Cite as

Jérôme Taupin. Estimation of Conformal Metrics. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 92:1-92:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{taupin:LIPIcs.SoCG.2026.92,
  author =	{Taupin, J\'{e}r\^{o}me},
  title =	{{Estimation of Conformal Metrics}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{92:1--92: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.92},
  URN =		{urn:nbn:de:0030-drops-258986},
  doi =		{10.4230/LIPIcs.SoCG.2026.92},
  annote =	{Keywords: Geometric inference, metric estimation, conformal metric, geodesics, sets of positive reach}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.93
Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations

Authors: Raphaël Tinarrage

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

Abstract
Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.
Cite as

Raphaël Tinarrage. Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 93:1-93:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tinarrage:LIPIcs.SoCG.2026.93,
  author =	{Tinarrage, Rapha\"{e}l},
  title =	{{Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{93:1--93:22},
  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.93},
  URN =		{urn:nbn:de:0030-drops-258991},
  doi =		{10.4230/LIPIcs.SoCG.2026.93},
  annote =	{Keywords: Triangulation of manifolds, Simplicial approximation, CW complexes, Delaunay complexes, List homomorphism problem, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.5
Bifunction and Interlevel Delaunay Trifiltrations

Authors: Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, and Abhishek Rathod

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

Abstract
A key property of the Delaunay filtration is that it is topologically (i.e., weakly) equivalent to the offset (union-of-balls) filtration. Recently, this filtration has been extended to point clouds equipped with an ℝ-valued function, yielding a computable 2-parameter filtration that satisfies an analogous weak equivalence. Motivated in part by the study of time-varying data, we introduce a 3-parameter extension of the Delaunay filtration for point clouds equipped with an ℝ²-valued function, also satisfying an analogous weak equivalence. For a point cloud X ⊂ ℝ^d, our trifiltration has size O(|X|^{⌈(d+1)/2⌉+1}). We present an algorithm that computes this trifiltration in time O(|X|^{⌈d/2⌉+2}), together with an implementation. Our experiments demonstrate that the implementation can handle thousands of points in ℝ³, with memory growth that is nearly linear.
Cite as

Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, and Abhishek Rathod. Bifunction and Interlevel Delaunay Trifiltrations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alonso_et_al:LIPIcs.SoCG.2026.5,
  author =	{Alonso, \'{A}ngel Javier and Kerber, Michael and Lam, Tung and Lesnick, Michael and Rathod, Abhishek},
  title =	{{Bifunction and Interlevel Delaunay Trifiltrations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{5:1--5:20},
  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.5},
  URN =		{urn:nbn:de:0030-drops-258118},
  doi =		{10.4230/LIPIcs.SoCG.2026.5},
  annote =	{Keywords: Delaunay triangulation, Multiparameter persistent homology, Interlevel, Bowyer-Watson}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.13
Line Cover and Related Problems

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994].
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana. Line Cover and Related Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.13,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Saha, Souvik and Seetharaman, Sanjay and Upasana, Anannya},
  title =	{{Line Cover and Related Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.13},
  URN =		{urn:nbn:de:0030-drops-255023},
  doi =		{10.4230/LIPIcs.STACS.2026.13},
  annote =	{Keywords: Point Line Cover, Projective Clustering, W-hardness, XP algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.31
Delaunay Triangulations with Predictions

Authors: Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set P of n points in the plane and a triangulation G that serves as a "prediction" of the Delaunay triangulation, we would like to use G to compute the correct Delaunay triangulation DT(P) more quickly when G is "close" to DT(P). We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1) Define D to be the number of edges in G that are not in DT(P). We present a deterministic algorithm to compute DT(P) from G in O(n + Dlog³ n) time, and a randomized algorithm in O(n+Dlog n) expected time, the latter of which is optimal in terms of D. 2) Let R be a random subset of the edges of DT(P), where each edge is chosen independently with probability ρ. Suppose G is any triangulation of P that contains R. We present an algorithm to compute DT(P) from G in O(nlog log n + nlog(1/ρ)) time with high probability. 3) Define d_{vio} to be the maximum number of points of P strictly inside the circumcircle of a triangle in G (the number is 0 if G is equal to DT(P)). We present a deterministic algorithm to compute DT(P) from G in O(nlog^*n + nlog d_{vio}) time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.
Cite as

Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos. Delaunay Triangulations with Predictions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 31:1-31:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ITCS.2026.31,
  author =	{Cabello, Sergio and Chan, Timothy M. and Giannopoulos, Panos},
  title =	{{Delaunay Triangulations with Predictions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{31:1--31:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.31},
  URN =		{urn:nbn:de:0030-drops-253186},
  doi =		{10.4230/LIPIcs.ITCS.2026.31},
  annote =	{Keywords: Delaunay Triangulation, Minimum Spanning Tree, Algorithms with Predictions}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.45
Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences

Authors: Tuyen Pham and Hubert Wagner

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
The contributions of the paper span theoretical and implementational results. First, we prove that Kd-trees can be extended to ℝ^d with the distance measured by an arbitrary Bregman divergence. Perhaps surprisingly, this shows that the triangle inequality is not necessary for correct pruning in Kd-trees. Second, we offer an efficient algorithm and C++ implementation for nearest neighbour search for decomposable Bregman divergences. The implementation supports the Kullback-Leibler divergence (relative entropy) which is a popular distance between probability vectors and is commonly used in statistics and machine learning. This is a step toward broadening the usage of computational geometry algorithms. Our benchmarks show that our implementation efficiently handles both exact and approximate nearest neighbour queries. Compared to a linear search, we achieve two orders of magnitude speedup for practical scenarios in dimension up to 100. Our solution is simpler and more efficient than competing methods.
Cite as

Tuyen Pham and Hubert Wagner. Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pham_et_al:LIPIcs.WADS.2025.45,
  author =	{Pham, Tuyen and Wagner, Hubert},
  title =	{{Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.45},
  URN =		{urn:nbn:de:0030-drops-242766},
  doi =		{10.4230/LIPIcs.WADS.2025.45},
  annote =	{Keywords: Kd-tree, k-d tree, nearest neighbour search, Bregman divergence, decomposable Bregman divergence, KL divergence, relative entropy, cross entropy, Shannon’s entropy}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.11
When Alpha-Complexes Collapse onto Codimension-1 Submanifolds

Authors: Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a finite set of points P sampling an unknown smooth surface ℳ ⊆ ℝ³, our goal is to triangulate ℳ based solely on P. Assuming ℳ is a smooth orientable submanifold of codimension 1 in ℝ^d, we introduce a simple algorithm, Naive Squash, which simplifies the α-complex of P by repeatedly applying a new type of collapse called vertical relative to ℳ. Naive Squash also has a practical version that does not require knowledge of ℳ. We establish conditions under which both the naive and practical Squash algorithms output a triangulation of ℳ. We provide a bound on the angle formed by triangles in the α-complex with ℳ, yielding sampling conditions on P that are competitive with existing literature for smooth surfaces embedded in ℝ³, while offering a more compartmentalized proof. As a by-product, we obtain that the restricted Delaunay complex of P triangulates ℳ when ℳ is a smooth surface in ℝ³ under weaker conditions than existing ones.
Cite as

Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier. When Alpha-Complexes Collapse onto Codimension-1 Submanifolds. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2025.11,
  author =	{Attali, Dominique and Cl\'{e}mot, Matt\'{e}o and Dornelas, Bianca B. and Lieutier, Andr\'{e}},
  title =	{{When Alpha-Complexes Collapse onto Codimension-1 Submanifolds}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.11},
  URN =		{urn:nbn:de:0030-drops-231630},
  doi =		{10.4230/LIPIcs.SoCG.2025.11},
  annote =	{Keywords: Submanifold reconstruction, triangulation, abstract simplicial complexes, collapses, convexity}
}
  • Refine by Type
  • 34 Document/PDF
  • 18 Document/HTML

  • Refine by Publication Year
  • 13 2026
  • 5 2025
  • 4 2024
  • 1 2021
  • 3 2020
  • Show More...

  • Refine by Author
  • 14 Boissonnat, Jean-Daniel
  • 10 Wintraecken, Mathijs
  • 7 Lieutier, André
  • 5 Dutta, Kunal
  • 4 Pritam, Siddharth
  • Show More...

  • Refine by Series/Journal
  • 34 LIPIcs

  • Refine by Classification
  • 23 Theory of computation → Computational geometry
  • 3 Mathematics of computing
  • 3 Mathematics of computing → Algebraic topology
  • 3 Mathematics of computing → Topology
  • 2 Theory of computation
  • Show More...

  • Refine by Keyword
  • 6 Topological Data Analysis
  • 5 Persistent homology
  • 4 Computational Topology
  • 4 Reach
  • 3 Manifolds
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact