DROPS

Document

DOI: 10.4230/LIPIcs.GD.2024.3

The Euclidean MST-Ratio for Bi-Colored Lattices

Authors: Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner, and Morteza Saghafian

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract

Given a finite set, A ⊆ ℝ², and a subset, B ⊆ A, the MST-ratio is the combined length of the minimum spanning trees of B and A⧵B divided by the length of the minimum spanning tree of A. The question of the supremum, over all sets A, of the maximum, over all subsets B, is related to the Steiner ratio, and we prove this sup-max is between 2.154 and 2.427. Restricting ourselves to 2-dimensional lattices, we prove that the sup-max is 2, while the inf-max is 1.25. By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than 1.25.

Cite as

Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. The Euclidean MST-Ratio for Bi-Colored Lattices. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cultreradimontesano_et_al:LIPIcs.GD.2024.3,
  author =	{Cultrera di Montesano, Sebastiano and Draganov, Ond\v{r}ej and Edelsbrunner, Herbert and Saghafian, Morteza},
  title =	{{The Euclidean MST-Ratio for Bi-Colored Lattices}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.3},
  URN =		{urn:nbn:de:0030-drops-212878},
  doi =		{10.4230/LIPIcs.GD.2024.3},
  annote =	{Keywords: Minimum spanning Trees, Steiner Ratio, Lattices, Partitions}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2021.16

Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory

Authors: Ranita Biswas, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian

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

Abstract

Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation.

Cite as

Ranita Biswas, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{biswas_et_al:LIPIcs.SoCG.2021.16,
  author =	{Biswas, Ranita and Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza},
  title =	{{Counting Cells of Order-k Voronoi Tessellations in \mathbb{R}³ with Morse Theory}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{16:1--16:15},
  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.16},
  URN =		{urn:nbn:de:0030-drops-138152},
  doi =		{10.4230/LIPIcs.SoCG.2021.16},
  annote =	{Keywords: Voronoi tessellations, Delaunay mosaics, arrangements, convex polytopes, Morse theory, counting}
}

Search Results

Documents authored by Cultrera di Montesano, Sebastiano

The Euclidean MST-Ratio for Bi-Colored Lattices

Abstract

Cite as

Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory

Abstract

Cite as

Thanks for your feedback!

Could not send message