Search Results

Documents authored by Despré, Vincent

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.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.ESA.2018.22
Improved Routing on the Delaunay Triangulation

Authors: Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despré, Darryl Hill, and Michiel Smid

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
A geometric graph G=(P,E) is a set of points in the plane and edges between pairs of points, where the weight of an edge is equal to the Euclidean distance between its two endpoints. In local routing we find a path through G from a source vertex s to a destination vertex t, using only knowledge of the current vertex, its incident edges, and the locations of s and t. We present an algorithm for local routing on the Delaunay triangulation, and show that it finds a path between a source vertex s and a target vertex t that is not longer than 3.56|st|, improving the previous bound of 5.9|st|.
Cite as

Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despré, Darryl Hill, and Michiel Smid. Improved Routing on the Delaunay Triangulation. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bonichon_et_al:LIPIcs.ESA.2018.22,
  author =	{Bonichon, Nicolas and Bose, Prosenjit and De Carufel, Jean-Lou and Despr\'{e}, Vincent and Hill, Darryl and Smid, Michiel},
  title =	{{Improved Routing on the Delaunay Triangulation}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.22},
  URN =		{urn:nbn:de:0030-drops-94857},
  doi =		{10.4230/LIPIcs.ESA.2018.22},
  annote =	{Keywords: Delaunay, local routing, geometric, graph}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.35
Computing the Geometric Intersection Number of Curves

Authors: Vincent Despré and Francis Lazarus

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

Abstract
The geometric intersection number of a curve on a surface is the minimal number of self-intersections of any homotopic curve, i.e. of any curve obtained by continuous deformation. Given a curve c represented by a closed walk of length at most l on a combinatorial surface of complexity n we describe simple algorithms to (1) compute the geometric intersection number of c in O(n+ l^2) time, (2) construct a curve homotopic to c that realizes this geometric intersection number in O(n+l^4) time, (3) decide if the geometric intersection number of c is zero, i.e. if c is homotopic to a simple curve, in O(n+l log^2 l) time. To our knowledge, no exact complexity analysis had yet appeared on those problems. An optimistic analysis of the complexity of the published algorithms for problems (1) and (3) gives at best a O(n+g^2l^2) time complexity on a genus g surface without boundary. No polynomial time algorithm was known for problem (2). Interestingly, our solution to problem (3) is the first quasi-linear algorithm since the problem was raised by Poincare more than a century ago. Finally, we note that our algorithm for problem (1) extends to computing the geometric intersection number of two curves of length at most l in O(n+ l^2) time.
Cite as

Vincent Despré and Francis Lazarus. Computing the Geometric Intersection Number of Curves. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{despre_et_al:LIPIcs.SoCG.2017.35,
  author =	{Despr\'{e}, Vincent and Lazarus, Francis},
  title =	{{Computing the Geometric Intersection Number of Curves}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{35:1--35: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.35},
  URN =		{urn:nbn:de:0030-drops-71838},
  doi =		{10.4230/LIPIcs.SoCG.2017.35},
  annote =	{Keywords: computational topology, curves on surfaces, combinatorial geodesic}
}
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