Search Results

Documents authored by Teillaud, Monique

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.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}
}
Document
DOI: 10.4230/DagRep.3.3.1
Computational Geometry (Dagstuhl Seminar 13101)

Authors: Otfried Cheong, Kurt Mehlhorn, and Monique Teillaud

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

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13101 "Computational Geometry". The seminar was held from 3rd to 8th March 2013 and 47 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. This report collects abstracts of the talks and a list of open problems.
Cite as

Otfried Cheong, Kurt Mehlhorn, and Monique Teillaud. Computational Geometry (Dagstuhl Seminar 13101). In Dagstuhl Reports, Volume 3, Issue 3, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{cheong_et_al:DagRep.3.3.1,
  author =	{Cheong, Otfried and Mehlhorn, Kurt and Teillaud, Monique},
  title =	{{Computational Geometry (Dagstuhl Seminar 13101)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{3},
  editor =	{Cheong, Otfried and Mehlhorn, Kurt 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.3.1},
  URN =		{urn:nbn:de:0030-drops-40210},
  doi =		{10.4230/DagRep.3.3.1},
  annote =	{Keywords: Algorithms, geometry, theory, approximation, implementation, combinatorics, topology}
}
Document
DOI: 10.4230/DagRep.1.3.19
Computational Geometry (Dagstuhl Seminar 11111)

Authors: Pankaj Kumar Agarwal, Kurt Mehlhorn, and Monique Teillaud

Published in: Dagstuhl Reports, Volume 1, Issue 3 (2011)

Abstract
This report documents the outcomes of Dagstuhl Seminar 11111 ``Computational Geometry''. The Seminar gathered fifty-three senior and younger researchers from various countries in the unique atmosphere offered by Schloss Dagstuhl. Abstracts of talks are collected in this report as well as a list of open problems.
Cite as

Pankaj Kumar Agarwal, Kurt Mehlhorn, and Monique Teillaud. Computational Geometry (Dagstuhl Seminar 11111). In Dagstuhl Reports, Volume 1, Issue 3, pp. 19-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{agarwal_et_al:DagRep.1.3.19,
  author =	{Agarwal, Pankaj Kumar and Mehlhorn, Kurt and Teillaud, Monique},
  title =	{{Computational Geometry (Dagstuhl Seminar 11111)}},
  pages =	{19--41},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{3},
  editor =	{Agarwal, Pankaj Kumar and Mehlhorn, Kurt 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.1.3.19},
  URN =		{urn:nbn:de:0030-drops-31997},
  doi =		{10.4230/DagRep.1.3.19},
  annote =	{Keywords: Algorithms, geometry, combinatorics, topology, theory, applications, implementation}
}
Document
DOI: 10.4230/DagSemProc.09111.1
09111 Abstracts Collection – Computational Geometry

Authors: Pankaj Kumar Agarwal, Helmut Alt, and Monique Teillaud

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)

Abstract
From March 8 to March 13, 2009, the Dagstuhl Seminar 09111 ``Computational Geometry '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Pankaj Kumar Agarwal, Helmut Alt, and Monique Teillaud. 09111 Abstracts Collection – Computational Geometry. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:DagSemProc.09111.1,
  author =	{Agarwal, Pankaj Kumar and Alt, Helmut and Teillaud, Monique},
  title =	{{09111 Abstracts Collection – Computational Geometry}},
  booktitle =	{Computational Geometry},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.1},
  URN =		{urn:nbn:de:0030-drops-20346},
  doi =		{10.4230/DagSemProc.09111.1},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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