Search Results

Documents authored by Cultrera di Montesano, Sebastiano

Document
DOI: 10.4230/LIPIcs.SoCG.2025.71
Banana Trees for the Persistence in Time Series Experimentally

Authors: Lara Ost, Sebastiano Cultrera di Montesano, and Herbert Edelsbrunner

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

Abstract
In numerous fields, dynamic time series data require continuous updates, necessitating efficient data processing techniques for accurate analysis. This paper examines the banana tree data structure, specifically designed to efficiently maintain the multi-scale topological descriptor commonly known as persistent homology for dynamically changing time series data. We implement this data structure and conduct an experimental study to assess its properties and runtime for update operations. Our findings indicate that banana trees are highly effective with unbiased random data, outperforming state-of-the-art static algorithms in these scenarios. Additionally, our results show that real-world time series share structural properties with unbiased random walks, suggesting potential practical utility for our implementation.
Cite as

Lara Ost, Sebastiano Cultrera di Montesano, and Herbert Edelsbrunner. Banana Trees for the Persistence in Time Series Experimentally. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 71:1-71:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ost_et_al:LIPIcs.SoCG.2025.71,
  author =	{Ost, Lara and Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert},
  title =	{{Banana Trees for the Persistence in Time Series Experimentally}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{71:1--71:13},
  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.71},
  URN =		{urn:nbn:de:0030-drops-232237},
  doi =		{10.4230/LIPIcs.SoCG.2025.71},
  annote =	{Keywords: persistent homology, time series, data structures, computational experiments}
}
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}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact