23 Search Results for "Teillaud, Monique"

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.ESA.2025.61
ε-Net Algorithm Implementation on Hyperbolic Surfaces

Authors: Vincent Despré, Camille Lanuel, Marc Pouget, and Monique Teillaud

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We propose an implementation, using the CGAL library, of an algorithm to compute ε-nets on hyperbolic surfaces proposed by Despré, Lanuel and Teillaud [Despré et al., 2024]. We describe the data structure, detail the implemented algorithm and report experimental results on hyperbolic surfaces of genus 2. The implementation differs from the cited algorithm on several aspects. In particular, we use a different data structure, based on combinatorial maps, to represent a triangulation of a surface. We explain how to generate fundamental polygons to represent our input hyperbolic surfaces and the arithmetic issues related to the number type of the coordinates of their vertices.
Cite as

Vincent Despré, Camille Lanuel, Marc Pouget, and Monique Teillaud. ε-Net Algorithm Implementation on Hyperbolic Surfaces. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 61:1-61:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{despre_et_al:LIPIcs.ESA.2025.61,
  author =	{Despr\'{e}, Vincent and Lanuel, Camille and Pouget, Marc and Teillaud, Monique},
  title =	{{\epsilon-Net Algorithm Implementation on Hyperbolic Surfaces}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{61:1--61:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.61},
  URN =		{urn:nbn:de:0030-drops-245296},
  doi =		{10.4230/LIPIcs.ESA.2025.61},
  annote =	{Keywords: Hyperbolic surface, Delaunay triangulation, Data structure, Combinatorial map, Implementation, CGAL}
}
Artifact
Software
DOI: 10.4230/artifacts.24672
Implementation of the ε-net algorithm

Authors: Vincent Despré, Camille Lanuel, Marc Pouget, and Monique Teillaud

Abstract
Cite as

Vincent Despré, Camille Lanuel, Marc Pouget, Monique Teillaud. Implementation of the ε-net algorithm (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24672,
   title = {{Implementation of the \epsilon-net algorithm}}, 
   author = {Despr\'{e}, Vincent and Lanuel, Camille and Pouget, Marc and Teillaud, Monique},
   note = {Software, ANR Abysm, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:2fab64276f7d193b0b712c135fa9eebba62f0509;origin=https://github.com/camille-lanuel/ESA_2025_implementation_epsilon_net;visit=swh:1:snp:746a88c723aa2bdc5fda86b1aab596931229dcb5;anchor=swh:1:rev:a97883aef3bfd9ee69ee5dbb8ec117ddc72f7686}{\texttt{swh:1:dir:2fab64276f7d193b0b712c135fa9eebba62f0509}} (visited on 2025-10-01)},
   url = {https://github.com/camille-lanuel/ESA_2025_implementation_epsilon_net},
   doi = {10.4230/artifacts.24672},
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.31
A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Authors: Timothy M. Chan and Isaac M. Hair

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

Abstract
Given two convex polygons P and Q with n and m edges, the maximum overlap problem is to find a translation of P that maximizes the area of its intersection with Q. We give the first randomized algorithm for this problem with linear running time. Our result improves the previous two-and-a-half-decades-old algorithm by de Berg, Cheong, Devillers, van Kreveld, and Teillaud (1998), which ran in O((n+m)log(n+m)) time, as well as multiple recent algorithms given for special cases of the problem.
Cite as

Timothy M. Chan and Isaac M. Hair. A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2025.31,
  author =	{Chan, Timothy M. and Hair, Isaac M.},
  title =	{{A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{31:1--31:16},
  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.31},
  URN =		{urn:nbn:de:0030-drops-231832},
  doi =		{10.4230/LIPIcs.SoCG.2025.31},
  annote =	{Keywords: Convex polygons, shape matching, prune-and-search, parametric search}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.59
Incremental Planar Nearest Neighbor Queries with Optimal Query Time

Authors: John Iacono and Yakov Nekrich

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

Abstract
In this paper we show that two-dimensional nearest neighbor queries can be answered in optimal O(log n) time while supporting insertions in O(log^{1+ε} n) time. No previous data structure was known that supports O(log n)-time queries and polylog-time insertions. In order to achieve logarithmic queries our data structure uses a new technique related to fractional cascading that leverages the inherent geometry of this problem. Our method can be also used in other semi-dynamic scenarios.
Cite as

John Iacono and Yakov Nekrich. Incremental Planar Nearest Neighbor Queries with Optimal Query Time. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{iacono_et_al:LIPIcs.SoCG.2025.59,
  author =	{Iacono, John and Nekrich, Yakov},
  title =	{{Incremental Planar Nearest Neighbor Queries with Optimal Query Time}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{59:1--59:15},
  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.59},
  URN =		{urn:nbn:de:0030-drops-232117},
  doi =		{10.4230/LIPIcs.SoCG.2025.59},
  annote =	{Keywords: Data Structures, Dynamic Data Structures, Nearest Neighbor Queries}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.46
Non-Euclidean Erdős-Anning Theorems

Authors: David Eppstein

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

Abstract
The Erdős-Anning theorem states that every point set in the Euclidean plane with integer distances must be either collinear or finite. More strongly, for any (non-degenerate) triangle of diameter δ, at most O(δ²) points can have integer distances from all three triangle vertices. We prove the same results for any strictly convex distance function on the plane, and analogous results for every two-dimensional complete Riemannian manifold of bounded genus and for geodesic distance on the boundary of every three-dimensional Euclidean convex set. As a consequence, we resolve a 1983 question of Richard Guy on the equilateral dimension of Riemannian manifolds. Our proofs are based on the properties of additively weighted Voronoi diagrams of these distances.
Cite as

David Eppstein. Non-Euclidean Erdős-Anning Theorems. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.SoCG.2025.46,
  author =	{Eppstein, David},
  title =	{{Non-Euclidean Erd\H{o}s-Anning Theorems}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{46:1--46:15},
  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.46},
  URN =		{urn:nbn:de:0030-drops-231983},
  doi =		{10.4230/LIPIcs.SoCG.2025.46},
  annote =	{Keywords: integer distances, additively weighted Voronoi diagrams, convex distance functions, Riemannian manifolds, geodesic distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.27
Computing a Dirichlet Domain for a Hyperbolic Surface

Authors: Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
This paper exhibits and analyzes an algorithm that takes a given closed orientable hyperbolic surface and outputs an explicit Dirichlet domain. The input is a fundamental polygon with side pairings. While grounded in topological considerations, the algorithm makes key use of the geometry of the surface. We introduce data structures that reflect this interplay between geometry and topology and show that the algorithm runs in polynomial time, in terms of the initial perimeter and the genus of the surface.
Cite as

Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud. Computing a Dirichlet Domain for a Hyperbolic Surface. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{despre_et_al:LIPIcs.SoCG.2023.27,
  author =	{Despr\'{e}, Vincent and Kolbe, Benedikt and Parlier, Hugo and Teillaud, Monique},
  title =	{{Computing a Dirichlet Domain for a Hyperbolic Surface}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.27},
  URN =		{urn:nbn:de:0030-drops-178771},
  doi =		{10.4230/LIPIcs.SoCG.2023.27},
  annote =	{Keywords: Hyperbolic geometry, Topology, Voronoi diagram, Algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.31
Minimal Delaunay Triangulations of Hyperbolic Surfaces

Authors: Matthijs Ebbens, Hugo Parlier, and Gert Vegter

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Motivated by recent work on Delaunay triangulations of hyperbolic surfaces, we consider the minimal number of vertices of such triangulations. First, we show that every hyperbolic surface of genus g has a simplicial Delaunay triangulation with O(g) vertices, where edges are given by distance paths. Then, we construct a class of hyperbolic surfaces for which the order of this bound is optimal. Finally, to give a general lower bound, we show that the Ω(√g) lower bound for the number of vertices of a simplicial triangulation of a topological surface of genus g is tight for hyperbolic surfaces as well.
Cite as

Matthijs Ebbens, Hugo Parlier, and Gert Vegter. Minimal Delaunay Triangulations of Hyperbolic Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ebbens_et_al:LIPIcs.SoCG.2021.31,
  author =	{Ebbens, Matthijs and Parlier, Hugo and Vegter, Gert},
  title =	{{Minimal Delaunay Triangulations of Hyperbolic Surfaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.31},
  URN =		{urn:nbn:de:0030-drops-138305},
  doi =		{10.4230/LIPIcs.SoCG.2021.31},
  annote =	{Keywords: Delaunay triangulations, hyperbolic surfaces, metric graph embeddings, moduli spaces}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.75
Generalizing CGAL Periodic Delaunay Triangulations

Authors: Georg Osang, Mael Rouxel-Labbé, and Monique Teillaud

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity.
Cite as

Georg Osang, Mael Rouxel-Labbé, and Monique Teillaud. Generalizing CGAL Periodic Delaunay Triangulations. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 75:1-75:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{osang_et_al:LIPIcs.ESA.2020.75,
  author =	{Osang, Georg and Rouxel-Labb\'{e}, Mael and Teillaud, Monique},
  title =	{{Generalizing CGAL Periodic Delaunay Triangulations}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{75:1--75:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.75},
  URN =		{urn:nbn:de:0030-drops-129419},
  doi =		{10.4230/LIPIcs.ESA.2020.75},
  annote =	{Keywords: Delaunay triangulation, lattice, algorithm, software, experiments}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.35
Flipping Geometric Triangulations on Hyperbolic Surfaces

Authors: Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We consider geometric triangulations of surfaces, i.e., triangulations whose edges can be realized by disjoint geodesic segments. We prove that the flip graph of geometric triangulations with fixed vertices of a flat torus or a closed hyperbolic surface is connected. We give upper bounds on the number of edge flips that are necessary to transform any geometric triangulation on such a surface into a Delaunay triangulation.
Cite as

Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud. Flipping Geometric Triangulations on Hyperbolic Surfaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{despre_et_al:LIPIcs.SoCG.2020.35,
  author =	{Despr\'{e}, Vincent and Schlenker, Jean-Marc and Teillaud, Monique},
  title =	{{Flipping Geometric Triangulations on Hyperbolic Surfaces}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.35},
  URN =		{urn:nbn:de:0030-drops-121939},
  doi =		{10.4230/LIPIcs.SoCG.2020.35},
  annote =	{Keywords: Hyperbolic surface, Topology, Delaunay triangulation, Algorithm, Flip graph}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.44
Implementing Delaunay Triangulations of the Bolza Surface

Authors: Iordan Iordanov and Monique Teillaud

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The CGAL library offers software packages to compute Delaunay triangulations of the (flat) torus of genus one in two and three dimensions. To the best of our knowledge, there is no available software for the simplest possible extension, i.e., the Bolza surface, a hyperbolic manifold homeomorphic to a torus of genus two. In this paper, we present an implementation based on the theoretical results and the incremental algorithm proposed last year at SoCG by Bogdanov, Teillaud, and Vegter. We describe the representation of the triangulation, we detail the different steps of the algorithm, we study predicates, and report experimental results.
Cite as

Iordan Iordanov and Monique Teillaud. Implementing Delaunay Triangulations of the Bolza Surface. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{iordanov_et_al:LIPIcs.SoCG.2017.44,
  author =	{Iordanov, Iordan and Teillaud, Monique},
  title =	{{Implementing Delaunay Triangulations of the Bolza Surface}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.44},
  URN =		{urn:nbn:de:0030-drops-72173},
  doi =		{10.4230/LIPIcs.SoCG.2017.44},
  annote =	{Keywords: hyperbolic surface, Fuchsian group, arithmetic issues, Dehn's algorithm, CGAL}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.20
Delaunay Triangulations on Orientable Surfaces of Low Genus

Authors: Mikhail Bogdanov, Monique Teillaud, and Gert Vegter

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Earlier work on Delaunay triangulation of point sets on the 2D flat torus, which is locally isometric to the Euclidean plane, was based on lifting the point set to a locally isometric 9-sheeted covering space of the torus. Under mild conditions the Delaunay triangulation of the lifted point set, consisting of 9 copies of the input set, projects to the Delaunay triangulation of the input set. We improve and generalize this work. First we present a new construction based on an 8-sheeted covering space, which shows that eight copies suffice for the standard flat torus. Then we generalize this construction to the context of compact orientable surfaces of higher genus, which are locally isometric to the hyperbolic plane. We investigate more thoroughly the Bolza surface, homeomorphic to a sphere with two handles, both because it is the hyperbolic surface with lowest genus, and because triangulations on the Bolza surface have applications in various fields such as neuromathematics and cosmological models. While the general properties (existence results of appropriate covering spaces) show similarities with the results for the flat case, explicit constructions and their proofs are much more complex, even in the case of the apparently simple Bolza surface. One of the main reasons is the fact that two hyperbolic translations do not commute in general. To the best of our knowledge, the results in this paper are the first ones of this kind. The interest of our contribution lies not only in the results, but most of all in the construction of covering spaces itself and the study of their properties.
Cite as

Mikhail Bogdanov, Monique Teillaud, and Gert Vegter. Delaunay Triangulations on Orientable Surfaces of Low Genus. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.SoCG.2016.20,
  author =	{Bogdanov, Mikhail and Teillaud, Monique and Vegter, Gert},
  title =	{{Delaunay Triangulations on Orientable Surfaces of Low Genus}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.20},
  URN =		{urn:nbn:de:0030-drops-59129},
  doi =		{10.4230/LIPIcs.SoCG.2016.20},
  annote =	{Keywords: covering spaces, hyperbolic surfaces, finitely presented groups, Fuchsian groups, systole}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.33
Qualitative Symbolic Perturbation

Authors: Olivier Devillers, Menelaos Karavelas, and Monique Teillaud

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
In a classical Symbolic Perturbation scheme, degeneracies are handled by substituting some polynomials in epsilon for the inputs of a predicate. Instead of a single perturbation, we propose to use a sequence of (simpler) perturbations. Moreover, we look at their effects geometrically instead of algebraically; this allows us to tackle cases that were not tractable with the classical algebraic approach.
Cite as

Olivier Devillers, Menelaos Karavelas, and Monique Teillaud. Qualitative Symbolic Perturbation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{devillers_et_al:LIPIcs.SoCG.2016.33,
  author =	{Devillers, Olivier and Karavelas, Menelaos and Teillaud, Monique},
  title =	{{Qualitative Symbolic Perturbation}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.33},
  URN =		{urn:nbn:de:0030-drops-59259},
  doi =		{10.4230/LIPIcs.SoCG.2016.33},
  annote =	{Keywords: Robustness issues, Symbolic perturbations, Apollonius diagram}
}
Document
DOI: 10.4230/DagRep.5.3.41
Computational Geometry (Dagstuhl Seminar 15111)

Authors: Otfried Cheong, Jeff Erickson, and Monique Teillaud

Published in: Dagstuhl Reports, Volume 5, Issue 3 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15111 "Computational Geometry". The seminar was held from 8th to 13th March 2015 and 41 senior and young researchers from various countries and continents attended it. Recent developments in the field were presented and new challenges in computational geometry were identified.
Cite as

Otfried Cheong, Jeff Erickson, and Monique Teillaud. Computational Geometry (Dagstuhl Seminar 15111). In Dagstuhl Reports, Volume 5, Issue 3, pp. 41-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{cheong_et_al:DagRep.5.3.41,
  author =	{Cheong, Otfried and Erickson, Jeff and Teillaud, Monique},
  title =	{{Computational Geometry (Dagstuhl Seminar 15111)}},
  pages =	{41--62},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{3},
  editor =	{Cheong, Otfried and Erickson, Jeff and Teillaud, Monique},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.3.41},
  URN =		{urn:nbn:de:0030-drops-52689},
  doi =		{10.4230/DagRep.5.3.41},
  annote =	{Keywords: Algorithms, geometry, theory, approximation, implementation, combinatorics, topology}
}
Document
DOI: 10.4230/DagRep.3.4.34
Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151)

Authors: Stephen G. Kobourov, Martin Nöllenburg, and Monique Teillaud

Published in: Dagstuhl Reports, Volume 3, Issue 4 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13151 "Drawing Graphs and Maps with Curves". The seminar brought together 34 researchers from different areas such as graph drawing, information visualization, computational geometry, and cartography. During the seminar we started with seven overview talks on the use of curves in the different communities represented in the seminar. Abstracts of these talks are collected in this report. Six working groups formed around open research problems related to the seminar topic and we report about their findings. Finally, the seminar was accompanied by the art exhibition Bending Reality: Where Arc and Science Meet with 40 exhibits contributed by the seminar participants.
Cite as

Stephen G. Kobourov, Martin Nöllenburg, and Monique Teillaud. Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151). In Dagstuhl Reports, Volume 3, Issue 4, pp. 34-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{kobourov_et_al:DagRep.3.4.34,
  author =	{Kobourov, Stephen G. and N\"{o}llenburg, Martin and Teillaud, Monique},
  title =	{{Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151)}},
  pages =	{34--68},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{4},
  editor =	{Kobourov, Stephen G. and N\"{o}llenburg, Martin and Teillaud, Monique},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.4.34},
  URN =		{urn:nbn:de:0030-drops-41680},
  doi =		{10.4230/DagRep.3.4.34},
  annote =	{Keywords: graph drawing, information visualization, computational cartography, computational geometry}
}
  • Refine by Type
  • 22 Document/PDF
  • 5 Document/HTML
  • 1 Artifact

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2023
  • 1 2021
  • 2 2020
  • Show More...

  • Refine by Author
  • 13 Teillaud, Monique
  • 4 Despré, Vincent
  • 2 Agarwal, Pankaj Kumar
  • 2 Chan, Timothy M.
  • 2 Cheong, Otfried
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs
  • 4 DagRep
  • 6 DagSemProc

  • Refine by Classification
  • 9 Theory of computation → Computational geometry
  • 4 Mathematics of computing → Geometric topology
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graphs and surfaces
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 3 Algorithms
  • 3 CGAL
  • 3 Delaunay triangulation
  • 3 combinatorics
  • 3 geometry
  • 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