2 Search Results for "Ebbens, Matthijs"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.26
Algorithms for Length Spectra of Combinatorial Tori

Authors: Vincent Delecroix, Matthijs Ebbens, Francis Lazarus, and Ivan Yakovlev

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

Abstract
Consider a weighted, undirected graph cellularly embedded on a topological surface. The function assigning to each free homotopy class of closed curves the length of a shortest cycle within this homotopy class is called the marked length spectrum. The (unmarked) length spectrum is obtained by just listing the length values of the marked length spectrum in increasing order. In this paper, we describe algorithms for computing the (un)marked length spectra of graphs embedded on the torus. More specifically, we preprocess a weighted graph of complexity n in time O(n² log log n) so that, given a cycle with 𝓁 edges representing a free homotopy class, the length of a shortest homotopic cycle can be computed in O(𝓁+log n) time. Moreover, given any positive integer k, the first k values of its unmarked length spectrum can be computed in time O(k log n). Our algorithms are based on a correspondence between weighted graphs on the torus and polyhedral norms. In particular, we give a weight independent bound on the complexity of the unit ball of such norms. As an immediate consequence we can decide if two embedded weighted graphs have the same marked spectrum in polynomial time. We also consider the problem of comparing the unmarked spectra and provide a polynomial time algorithm in the unweighted case and a randomized polynomial time algorithm otherwise.
Cite as

Vincent Delecroix, Matthijs Ebbens, Francis Lazarus, and Ivan Yakovlev. Algorithms for Length Spectra of Combinatorial Tori. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{delecroix_et_al:LIPIcs.SoCG.2023.26,
  author =	{Delecroix, Vincent and Ebbens, Matthijs and Lazarus, Francis and Yakovlev, Ivan},
  title =	{{Algorithms for Length Spectra of Combinatorial Tori}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{26:1--26:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.26},
  URN =		{urn:nbn:de:0030-drops-178765},
  doi =		{10.4230/LIPIcs.SoCG.2023.26},
  annote =	{Keywords: graphs on surfaces, length spectrum, polyhedral norm}
}
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-dev.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}
}
  • Refine by Author
  • 2 Ebbens, Matthijs
  • 1 Delecroix, Vincent
  • 1 Lazarus, Francis
  • 1 Parlier, Hugo
  • 1 Vegter, Gert
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Geometric topology
  • 2 Mathematics of computing → Graphs and surfaces
  • 1 Mathematics of computing → Enumeration
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Delaunay triangulations
  • 1 graphs on surfaces
  • 1 hyperbolic surfaces
  • 1 length spectrum
  • 1 metric graph embeddings
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2023

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