Volume
LIPIcs, Volume 258
39th International Symposium on Computational Geometry (SoCG 2023)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG)
Event
SoCG 2023, June 12-15, 2023, Dallas, Texas, USAEditors
Publication Details
- published at: 2023-06-09
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-273-0
- DBLP: db/conf/compgeom/compgeom2023
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 258, SoCG 2023, Complete Volume
Abstract
LIPIcs, Volume 258, SoCG 2023, Complete Volume
Cite as
39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 1-1058, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@Proceedings{chambers_et_al:LIPIcs.SoCG.2023,
title = {{LIPIcs, Volume 258, SoCG 2023, Complete Volume}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {1--1058},
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},
URN = {urn:nbn:de:0030-drops-178498},
doi = {10.4230/LIPIcs.SoCG.2023},
annote = {Keywords: LIPIcs, Volume 258, SoCG 2023, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{chambers_et_al:LIPIcs.SoCG.2023.0,
author = {Chambers, Erin W. and Gudmundsson, Joachim},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {0:i--0:xx},
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.0},
URN = {urn:nbn:de:0030-drops-178501},
doi = {10.4230/LIPIcs.SoCG.2023.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Geometric Embeddability of Complexes Is ∃ℝ-Complete
Abstract
We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in ℝ^d is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d-1,d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.
Cite as
Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Geometric Embeddability of Complexes Is ∃ℝ-Complete. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.1,
author = {Abrahamsen, Mikkel and Kleist, Linda and Miltzow, Tillmann},
title = {{Geometric Embeddability of Complexes Is \exists\mathbb{R}-Complete}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {1:1--1:19},
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.1},
URN = {urn:nbn:de:0030-drops-178518},
doi = {10.4230/LIPIcs.SoCG.2023.1},
annote = {Keywords: simplicial complex, geometric embedding, linear embedding, hypergraph, recognition, existential theory of the reals}
}
Document
Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks
Abstract
For smooth convex disks A, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes G^{hom}(A) and G^{sim}(A) of intersection graphs that can be obtained from homothets and similarities of A, respectively. Namely, we prove that G^{hom}(A) = G^{hom}(B) if and only if A and B are affine equivalent, and G^{sim}(A) = G^{sim}(B) if and only if A and B are similar.
Cite as
Mikkel Abrahamsen and Bartosz Walczak. Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.2,
author = {Abrahamsen, Mikkel and Walczak, Bartosz},
title = {{Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {2:1--2: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.2},
URN = {urn:nbn:de:0030-drops-178523},
doi = {10.4230/LIPIcs.SoCG.2023.2},
annote = {Keywords: geometric intersection graph, convex disk, homothet, similarity}
}
Document
Lower Bounds for Intersection Reporting Among Flat Objects
Abstract
Recently, Ezra and Sharir [Esther Ezra and Micha Sharir, 2022] showed an O(n^{3/2+σ}) space and O(n^{1/2+σ}) query time data structure for ray shooting among triangles in ℝ³. This improves the upper bound given by the classical S(n)Q(n)⁴ = O(n^{4+σ}) space-time tradeoff for the first time in almost 25 years and in fact lies on the tradeoff curve of S(n)Q(n)³ = O(n^{3+σ}). However, it seems difficult to apply their techniques beyond this specific space and time combination. This pheonomenon appears persistently in almost all recent advances of flat object intersection searching, e.g., line-tetrahedron intersection in ℝ⁴ [Esther Ezra and Micha Sharir, 2022], triangle-triangle intersection in ℝ⁴ [Esther Ezra and Micha Sharir, 2022], or even among flat semialgebraic objects [Agarwal et al., 2022].
We give a timely explanation to this phenomenon from a lower bound perspective. We prove that given a set 𝒮 of (d-1)-dimensional simplicies in ℝ^d, any data structure that can report all intersections with a query line in small (n^o(1)) query time must use Ω(n^{2(d-1)-o(1)}) space. This dashes the hope of any significant improvement to the tradeoff curves for small query time and almost matches the classical upper bound. We also obtain an almost matching space lower bound of Ω(n^{6-o(1)}) for triangle-triangle intersection reporting in ℝ⁴ when the query time is small. Along the way, we further develop the previous lower bound techniques by Afshani and Cheng [Afshani and Cheng, 2021; Afshani and Cheng, 2022].
Cite as
Peyman Afshani and Pingan Cheng. Lower Bounds for Intersection Reporting Among Flat Objects. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{afshani_et_al:LIPIcs.SoCG.2023.3,
author = {Afshani, Peyman and Cheng, Pingan},
title = {{Lower Bounds for Intersection Reporting Among Flat Objects}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {3:1--3: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.3},
URN = {urn:nbn:de:0030-drops-178536},
doi = {10.4230/LIPIcs.SoCG.2023.3},
annote = {Keywords: Computational Geometry, Intersection Searching, Data Structure Lower Bounds}
}
Document
Computing Instance-Optimal Kernels in Two Dimensions
Abstract
Let P be a set of n points in ℝ². For a parameter ε ∈ (0,1), a subset C ⊆ P is an ε-kernel of P if the projection of the convex hull of C approximates that of P within (1-ε)-factor in every direction. The set C is a weak ε-kernel of P if its directional width approximates that of P in every direction. Let 𝗄_ε(P) (resp. 𝗄^𝗐_ε(P)) denote the minimum-size of an ε-kernel (resp. weak ε-kernel) of P. We present an O(n 𝗄_ε(P)log n)-time algorithm for computing an ε-kernel of P of size 𝗄_ε(P), and an O(n²log n)-time algorithm for computing a weak ε-kernel of P of size 𝗄^𝗐_ε(P). We also present a fast algorithm for the Hausdorff variant of this problem.
In addition, we introduce the notion of ε-core, a convex polygon lying inside ch(P), prove that it is a good approximation of the optimal ε-kernel, present an efficient algorithm for computing it, and use it to compute an ε-kernel of small size.
Cite as
Pankaj K. Agarwal and Sariel Har-Peled. Computing Instance-Optimal Kernels in Two Dimensions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2023.4,
author = {Agarwal, Pankaj K. and Har-Peled, Sariel},
title = {{Computing Instance-Optimal Kernels in Two Dimensions}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {4:1--4: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.4},
URN = {urn:nbn:de:0030-drops-178544},
doi = {10.4230/LIPIcs.SoCG.2023.4},
annote = {Keywords: Coreset, approximation, kernel}
}
Document
Line Intersection Searching Amid Unit Balls in 3-Space
Abstract
Let ℬ be a set of n unit balls in ℝ³. We present a linear-size data structure for storing ℬ that can determine in O^*(n^{1/2}) time whether a query line intersects any ball of ℬ and report all k such balls in additional O(k) time. The data structure can be constructed in O(n log n) time. (The O^*(⋅) notation hides subpolynomial factors, e.g., of the form O(n^ε), for arbitrarily small ε > 0, and their coefficients which depend on ε.)
We also consider the dual problem: Let ℒ be a set of n lines in ℝ³. We preprocess ℒ, in O^*(n²) time, into a data structure of size O^*(n²) that can determine in O^*(1) time whether a query unit ball intersects any line of ℒ, or report all k such lines in additional O(k) time.
Cite as
Pankaj K. Agarwal and Esther Ezra. Line Intersection Searching Amid Unit Balls in 3-Space. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2023.5,
author = {Agarwal, Pankaj K. and Ezra, Esther},
title = {{Line Intersection Searching Amid Unit Balls in 3-Space}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {5:1--5:14},
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.5},
URN = {urn:nbn:de:0030-drops-178559},
doi = {10.4230/LIPIcs.SoCG.2023.5},
annote = {Keywords: Intersection searching, cylindrical range searching, partition trees, union of cylinders}
}
Document
Drawings of Complete Multipartite Graphs up to Triangle Flips
Abstract
For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended rotation system (ERS) of the drawing is the collection of the rotations of all vertices and crossings. A drawing is simple if each pair of edges has at most one common point. Gioan’s Theorem states that for any two simple drawings of the complete graph K_n with the same crossing edge pairs, one drawing can be transformed into the other by a sequence of triangle flips (a.k.a. Reidemeister moves of Type 3). This operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite crossing of the cell, via a local transformation.
We investigate to what extent Gioan-type theorems can be obtained for wider classes of graphs. A necessary (but in general not sufficient) condition for two drawings of a graph to be transformable into each other by a sequence of triangle flips is that they have the same ERS. As our main result, we show that for the large class of complete multipartite graphs, this necessary condition is in fact also sufficient. We present two different proofs of this result, one of which is shorter, while the other one yields a polynomial time algorithm for which the number of needed triangle flips for graphs on n vertices is bounded by O(n^{16}). The latter proof uses a Carathéodory-type theorem for simple drawings of complete multipartite graphs, which we believe to be of independent interest.
Moreover, we show that our Gioan-type theorem for complete multipartite graphs is essentially tight in the following sense: For the complete bipartite graph K_{m,n} minus two edges and K_{m,n} plus one edge for any m,n ≥ 4, as well as K_n minus a 4-cycle for any n ≥ 5, there exist two simple drawings with the same ERS that cannot be transformed into each other using triangle flips. So having the same ERS does not remain sufficient when removing or adding very few edges.
Cite as
Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang, Michael Hoffmann, Jan Kynčl, Yannic Maus, Birgit Vogtenhuber, and Alexandra Weinberger. Drawings of Complete Multipartite Graphs up to Triangle Flips. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2023.6,
author = {Aichholzer, Oswin and Chiu, Man-Kwun and Hoang, Hung P. and Hoffmann, Michael and Kyn\v{c}l, Jan and Maus, Yannic and Vogtenhuber, Birgit and Weinberger, Alexandra},
title = {{Drawings of Complete Multipartite Graphs up to Triangle Flips}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {6:1--6: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.6},
URN = {urn:nbn:de:0030-drops-178563},
doi = {10.4230/LIPIcs.SoCG.2023.6},
annote = {Keywords: Simple drawings, simple topological graphs, complete graphs, multipartite graphs, k-partite graphs, bipartite graphs, Gioan’s Theorem, triangle flips, Reidemeister moves}
}
Document
Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets
Abstract
We study the decomposition of zero-dimensional persistence modules, viewed as functors valued in the category of vector spaces factorizing through sets. Instead of working directly at the level of vector spaces, we take a step back and first study the decomposition problem at the level of sets.
This approach allows us to define the combinatorial notion of rooted subsets. In the case of a filtered metric space M, rooted subsets relate the clustering behavior of the points of M with the decomposition of the associated persistence module. In particular, we can identify intervals in such a decomposition quickly. In addition, rooted subsets can be understood as a generalization of the elder rule, and are also related to the notion of constant conqueror of Cai, Kim, Mémoli and Wang. As an application, we give a lower bound on the number of intervals that we can expect in the decomposition of zero-dimensional persistence modules of a density-Rips filtration in Euclidean space: in the limit, and under very general circumstances, we can expect that at least 25% of the indecomposable summands are interval modules.
Cite as
Ángel Javier Alonso and Michael Kerber. Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{alonso_et_al:LIPIcs.SoCG.2023.7,
author = {Alonso, \'{A}ngel Javier and Kerber, Michael},
title = {{Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {7:1--7: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.7},
URN = {urn:nbn:de:0030-drops-178570},
doi = {10.4230/LIPIcs.SoCG.2023.7},
annote = {Keywords: Multiparameter persistent homology, Clustering, Decomposition of persistence modules, Elder Rule}
}
Document
On Helly Numbers of Exponential Lattices
Abstract
Given a set S ⊆ ℝ², define the Helly number of S, denoted by H(S), as the smallest positive integer N, if it exists, for which the following statement is true: for any finite family ℱ of convex sets in ℝ² such that the intersection of any N or fewer members of ℱ contains at least one point of S, there is a point of S common to all members of ℱ.
We prove that the Helly numbers of exponential lattices {αⁿ : n ∈ ℕ₀}² are finite for every α > 1 and we determine their exact values in some instances. In particular, we obtain H({2ⁿ : n ∈ ℕ₀}²) = 5, solving a problem posed by Dillon (2021).
For real numbers α, β > 1, we also fully characterize exponential lattices L(α,β) = {αⁿ : n ∈ ℕ₀} × {βⁿ : n ∈ ℕ₀} with finite Helly numbers by showing that H(L(α,β)) is finite if and only if log_α(β) is rational.
Cite as
Gergely Ambrus, Martin Balko, Nóra Frankl, Attila Jung, and Márton Naszódi. On Helly Numbers of Exponential Lattices. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{ambrus_et_al:LIPIcs.SoCG.2023.8,
author = {Ambrus, Gergely and Balko, Martin and Frankl, N\'{o}ra and Jung, Attila and Nasz\'{o}di, M\'{a}rton},
title = {{On Helly Numbers of Exponential Lattices}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {8:1--8: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.8},
URN = {urn:nbn:de:0030-drops-178584},
doi = {10.4230/LIPIcs.SoCG.2023.8},
annote = {Keywords: Helly numbers, exponential lattices, Diophantine approximation}
}
Document
Optimal Volume-Sensitive Bounds for Polytope Approximation
Abstract
Approximating convex bodies is a fundamental question in geometry and has a wide variety of applications. Consider a convex body K of diameter Δ in ℝ^d for fixed d. The objective is to minimize the number of vertices (alternatively, the number of facets) of an approximating polytope for a given Hausdorff error ε. It is known from classical results of Dudley (1974) and Bronshteyn and Ivanov (1976) that Θ((Δ/ε)^{(d-1)/2}) vertices (alternatively, facets) are both necessary and sufficient. While this bound is tight in the worst case, that of Euclidean balls, it is far from optimal for skinny convex bodies.
A natural way to characterize a convex object’s skinniness is in terms of its relationship to the Euclidean ball. Given a convex body K, define its volume diameter Δ_d to be the diameter of a Euclidean ball of the same volume as K, and define its surface diameter Δ_{d-1} analogously for surface area. It follows from generalizations of the isoperimetric inequality that Δ ≥ Δ_{d-1} ≥ Δ_d.
Arya, da Fonseca, and Mount (SoCG 2012) demonstrated that the diameter-based bound could be made surface-area sensitive, improving the above bound to O((Δ_{d-1}/ε)^{(d-1)/2}). In this paper, we strengthen this by proving the existence of an approximation with O((Δ_d/ε)^{(d-1)/2}) facets.
This improvement is a result of the combination of a number of new ideas. As in prior work, we exploit properties of the original body and its polar dual. In order to obtain a volume-sensitive bound, we explore the following more general problem. Given two convex bodies, one nested within the other, find a low-complexity convex polytope that is sandwiched between them. We show that this problem can be reduced to a covering problem involving a natural intermediate body based on the harmonic mean. Our proof relies on a geometric analysis of a relative notion of fatness involving these bodies.
Cite as
Sunil Arya and David M. Mount. Optimal Volume-Sensitive Bounds for Polytope Approximation. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{arya_et_al:LIPIcs.SoCG.2023.9,
author = {Arya, Sunil and Mount, David M.},
title = {{Optimal Volume-Sensitive Bounds for Polytope Approximation}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {9:1--9: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.9},
URN = {urn:nbn:de:0030-drops-178592},
doi = {10.4230/LIPIcs.SoCG.2023.9},
annote = {Keywords: Approximation algorithms, convexity, Macbeath regions}
}
Document
Coresets for Clustering in Geometric Intersection Graphs
Abstract
Designing coresets - small-space sketches of the data preserving cost of the solutions within (1± ε)-approximate factor - is an important research direction in the study of center-based k-clustering problems, such as k-means or k-median. Feldman and Langberg [STOC'11] have shown that for k-clustering of n points in general metrics, it is possible to obtain coresets whose size depends logarithmically in n. Moreover, such a dependency in n is inevitable in general metrics. A significant amount of recent work in the area is devoted to obtaining coresests whose sizes are independent of n for special metrics, like d-dimensional Euclidean space [Huang, Vishnoi, STOC'20], doubling metrics [Huang, Jiang, Li, Wu, FOCS'18], metrics of graphs of bounded treewidth [Baker, Braverman, Huang, Jiang, Krauthgamer, Wu, ICML’20], or graphs excluding a fixed minor [Braverman, Jiang, Krauthgamer, Wu, SODA’21].
In this paper, we provide the first constructions of coresets whose size does not depend on n for k-clustering in the metrics induced by geometric intersection graphs. For example, we obtain (k log²k)/ε^𝒪(1) size coresets for k-clustering in Euclidean-weighted unit-disk graphs (UDGs) and unit-square graphs (USGs). These constructions follow from a general theorem that identifies two canonical properties of a graph metric sufficient for obtaining coresets whose size is independent of n. The proof of our theorem builds on the recent work of Cohen-Addad, Saulpic, and Schwiegelshohn [STOC '21], which ensures small-sized coresets conditioned on the existence of an interesting set of centers, called centroid set. The main technical contribution of our work is the proof of the existence of such a small-sized centroid set for graphs that satisfy the two canonical properties. Loosely speaking, the metrics of geometric intersection graphs are "similar" to the Euclidean metrics for points that are close, and to the shortest path metrics of planar graphs for points that are far apart. The main technical challenge in constructing centroid sets of small sizes is in combining these two very different metrics.
The new coreset construction helps to design the first (1+ε)-approximation for center-based clustering problems in UDGs and USGs, that is fixed-parameter tractable in k and ε (FPT-AS).
Cite as
Sayan Bandyapadhyay, Fedor V. Fomin, and Tanmay Inamdar. Coresets for Clustering in Geometric Intersection Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.10,
author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Inamdar, Tanmay},
title = {{Coresets for Clustering in Geometric Intersection Graphs}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {10:1--10: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.10},
URN = {urn:nbn:de:0030-drops-178605},
doi = {10.4230/LIPIcs.SoCG.2023.10},
annote = {Keywords: k-median, k-means, clustering, coresets, geometric graphs}
}
Document
Minimum-Membership Geometric Set Cover, Revisited
Abstract
We revisit a natural variant of the geometric set cover problem, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set S of points and a set ℛ of geometric objects, and the goal is to find a subset ℛ^* ⊆ ℛ to cover all points in S such that the membership of S with respect to ℛ^*, denoted by memb(S,ℛ^*), is minimized, where memb(S,ℛ^*) = max_{p ∈ S} |{R ∈ ℛ^*: p ∈ R}|. We give the first polynomial-time approximation algorithms for MMGSC in ℝ². Specifically, we achieve the following two main results.
- We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time n^{O(opt)} where opt is the optimum of the problem (i.e., the minimum membership).
- We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of o(log n) in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find ℛ^* ⊆ ℛ to cover S such that the ply of ℛ^* is minimized, where the ply is defined as the maximum number of objects in ℛ^* which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in O(n^{12}) time. We give a significantly simpler constant-approximation algorithm with near-linear running time.
Cite as
Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11,
author = {Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie},
title = {{Minimum-Membership Geometric Set Cover, Revisited}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {11:1--11:14},
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.11},
URN = {urn:nbn:de:0030-drops-178610},
doi = {10.4230/LIPIcs.SoCG.2023.11},
annote = {Keywords: geometric set cover, geometric optimization, approximation algorithms}
}
Document
FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
Abstract
Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approximation algorithm for the problem of clustering points in a general metric into k clusters to minimize the sum of cluster radii, subject to non-uniform hard capacity constraints (Capacitated Sum of Radii ). In particular, we give a (15+ε)-approximation algorithm that runs in 2^𝒪(k²log k) ⋅ n³ time.
When capacities are uniform, we obtain the following improved approximation bounds.
- A (4 + ε)-approximation with running time 2^𝒪(klog(k/ε)) n³, which significantly improves over the FPT 28-approximation of Inamdar and Varadarajan [ESA 2020].
- A (2 + ε)-approximation with running time 2^𝒪(k/ε² ⋅log(k/ε)) dn³ and a (1+ε)-approxim- ation with running time 2^𝒪(kdlog ((k/ε))) n³ in the Euclidean space. Here d is the dimension.
- A (1 + ε)-approximation in the Euclidean space with running time 2^𝒪(k/ε² ⋅log(k/ε)) dn³ if we are allowed to violate the capacities by (1 + ε)-factor. We complement this result by showing that there is no (1 + ε)-approximation algorithm running in time f(k)⋅ n^𝒪(1), if any capacity violation is not allowed.
Cite as
Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.12,
author = {Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket},
title = {{FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {12:1--12:14},
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.12},
URN = {urn:nbn:de:0030-drops-178628},
doi = {10.4230/LIPIcs.SoCG.2023.12},
annote = {Keywords: Clustering, FPT-approximation}
}
Document
Multilevel Skeletonization Using Local Separators
Abstract
In this paper we give a new, efficient algorithm for computing curve skeletons, based on local separators. Our efficiency stems from a multilevel approach, where we solve small problems across levels of detail and combine these in order to quickly obtain a skeleton. We do this in a highly modular fashion, ensuring complete flexibility in adapting the algorithm for specific types of input or for otherwise targeting specific applications.
Separator based skeletonization was first proposed by Bærentzen and Rotenberg in [ACM Tran. Graphics'21], showing high quality output at the cost of running times which become prohibitive for large inputs. Our new approach retains the high quality output, and applicability to any spatially embedded graph, while being orders of magnitude faster for all practical purposes.
We test our skeletonization algorithm for efficiency and quality in practice, comparing it to local separator skeletonization on the University of Groningen Skeletonization Benchmark [Telea'16].
Cite as
J. Andreas Bærentzen, Rasmus Emil Christensen, Emil Toftegaard Gæde, and Eva Rotenberg. Multilevel Skeletonization Using Local Separators. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{brentzen_et_al:LIPIcs.SoCG.2023.13,
author = {B{\ae}rentzen, J. Andreas and Christensen, Rasmus Emil and G{\ae}de, Emil Toftegaard and Rotenberg, Eva},
title = {{Multilevel Skeletonization Using Local Separators}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {13:1--13:18},
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.13},
URN = {urn:nbn:de:0030-drops-178637},
doi = {10.4230/LIPIcs.SoCG.2023.13},
annote = {Keywords: Algorithm engineering, experimentation and implementation, shape skeletonization, curve skeletons, multilevel algorithm}
}
Document
Efficient Computation of Image Persistence
Abstract
We present an algorithm for computing the barcode of the image of a morphism in persistent homology induced by an inclusion of filtered finite-dimensional chain complexes. The algorithm makes use of the clearing optimization and can be applied to inclusion-induced maps in persistent absolute homology and persistent relative cohomology for filtrations of pairs of simplicial complexes. The clearing optimization works particularly well in the context of relative cohomology, and using previous duality results we can translate the barcodes of images in relative cohomology to those in absolute homology. This forms the basis for an implementation of image persistence computations for inclusions of filtrations of Vietoris-Rips complexes in the framework of the software Ripser.
Cite as
Ulrich Bauer and Maximilian Schmahl. Efficient Computation of Image Persistence. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bauer_et_al:LIPIcs.SoCG.2023.14,
author = {Bauer, Ulrich and Schmahl, Maximilian},
title = {{Efficient Computation of Image Persistence}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {14:1--14:14},
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.14},
URN = {urn:nbn:de:0030-drops-178643},
doi = {10.4230/LIPIcs.SoCG.2023.14},
annote = {Keywords: Persistent homology, image persistence, barcode computation}
}
Document
Efficient Two-Parameter Persistence Computation via Cohomology
Abstract
Clearing is a simple but effective optimization for the standard algorithm of persistent homology (ph), which dramatically improves the speed and scalability of ph computations for Vietoris-Rips filtrations. Due to the quick growth of the boundary matrices of a Vietoris-Rips filtration with increasing dimension, clearing is only effective when used in conjunction with a dual (cohomological) variant of the standard algorithm. This approach has not previously been applied successfully to the computation of two-parameter ph.
We introduce a cohomological algorithm for computing minimal free resolutions of two-parameter ph that allows for clearing. To derive our algorithm, we extend the duality principles which underlie the one-parameter approach to the two-parameter setting. We provide an implementation and report experimental run times for function-Rips filtrations. Our method is faster than the current state-of-the-art by a factor of up to 20.
Cite as
Ulrich Bauer, Fabian Lenzen, and Michael Lesnick. Efficient Two-Parameter Persistence Computation via Cohomology. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bauer_et_al:LIPIcs.SoCG.2023.15,
author = {Bauer, Ulrich and Lenzen, Fabian and Lesnick, Michael},
title = {{Efficient Two-Parameter Persistence Computation via Cohomology}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {15:1--15:17},
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.15},
URN = {urn:nbn:de:0030-drops-178656},
doi = {10.4230/LIPIcs.SoCG.2023.15},
annote = {Keywords: Persistent homology, persistent cohomology, two-parameter persistence, clearing}
}
Document
The Complexity of Geodesic Spanners
Abstract
A geometric t-spanner for a set S of n point sites is an edge-weighted graph for which the (weighted) distance between any two sites p,q ∈ S is at most t times the original distance between p and q. We study geometric t-spanners for point sets in a constrained two-dimensional environment P. In such cases, the edges of the spanner may have non-constant complexity. Hence, we introduce a novel spanner property: the spanner complexity, that is, the total complexity of all edges in the spanner. Let S be a set of n point sites in a simple polygon P with m vertices. We present an algorithm to construct, for any constant ε > 0 and fixed integer k ≥ 1, a (2k + ε)-spanner with complexity O(mn^{1/k} + nlog² n) in O(nlog²n + mlog n + K) time, where K denotes the output complexity. When we consider sites in a polygonal domain P with holes, we can construct such a (2k+ε)-spanner of similar complexity in O(n² log m + nmlog m + K) time. Additionally, for any constant ε ∈ (0,1) and integer constant t ≥ 2, we show a lower bound for the complexity of any (t-ε)-spanner of Ω(mn^{1/(t-1)} + n).
Cite as
Sarita de Berg, Marc van Kreveld, and Frank Staals. The Complexity of Geodesic Spanners. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{deberg_et_al:LIPIcs.SoCG.2023.16,
author = {de Berg, Sarita and van Kreveld, Marc and Staals, Frank},
title = {{The Complexity of Geodesic Spanners}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {16:1--16: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.16},
URN = {urn:nbn:de:0030-drops-178669},
doi = {10.4230/LIPIcs.SoCG.2023.16},
annote = {Keywords: spanner, simple polygon, polygonal domain, geodesic distance, complexity}
}
Document
An Extension Theorem for Signotopes
Abstract
In 1926, Levi showed that, for every pseudoline arrangement 𝒜 and two points in the plane, 𝒜 can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in ℝ^d with a hyperplane containing d prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in ℝ³ which cannot be extended with a pseudoplane containing two particular prescribed points.
In this article, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. Our main result is that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them. Moreover, we conjecture that in all even ranks r ≥ 4 there exist signotopes which are not extendable for two prescribed points. Our conjecture is supported by examples in ranks 4, 6, 8, 10, and 12 that were found with a SAT based approach.
Cite as
Helena Bergold, Stefan Felsner, and Manfred Scheucher. An Extension Theorem for Signotopes. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bergold_et_al:LIPIcs.SoCG.2023.17,
author = {Bergold, Helena and Felsner, Stefan and Scheucher, Manfred},
title = {{An Extension Theorem for Signotopes}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {17:1--17:14},
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.17},
URN = {urn:nbn:de:0030-drops-178676},
doi = {10.4230/LIPIcs.SoCG.2023.17},
annote = {Keywords: arrangement of pseudolines, extendability, Levi’s extension lemma, arrangement of pseudohyperplanes, signotope, oriented matroid, partial order, Boolean satisfiability (SAT)}
}
Document
Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable
Abstract
The task of finding an extension to a given partial drawing of a graph while adhering to constraints on the representation has been extensively studied in the literature, with well-known results providing efficient algorithms for fundamental representations such as planar and beyond-planar topological drawings. In this paper, we consider the extension problem for bend-minimal orthogonal drawings of planar graphs, which is among the most fundamental geometric graph drawing representations. While the problem was known to be NP-hard, it is natural to consider the case where only a small part of the graph is still to be drawn. Here, we establish the fixed-parameter tractability of the problem when parameterized by the size of the missing subgraph. Our algorithm is based on multiple novel ingredients which intertwine geometric and combinatorial arguments. These include the identification of a new graph representation of bend-equivalent regions for vertex placement in the plane, establishing a bound on the treewidth of this auxiliary graph, and a global point-grid that allows us to discretize the possible placement of bends and vertices into locally bounded subgrids for each of the above regions.
Cite as
Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani, and Martin Nöllenburg. Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bhore_et_al:LIPIcs.SoCG.2023.18,
author = {Bhore, Sujoy and Ganian, Robert and Khazaliya, Liana and Montecchiani, Fabrizio and N\"{o}llenburg, Martin},
title = {{Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {18:1--18: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.18},
URN = {urn:nbn:de:0030-drops-178689},
doi = {10.4230/LIPIcs.SoCG.2023.18},
annote = {Keywords: orthogonal drawings, bend minimization, extension problems, parameterized complexity}
}
Document
Improved Bounds for Covering Paths and Trees in the Plane
Abstract
A covering path for a planar point set is a path drawn in the plane with straight-line edges such that every point lies at a vertex or on an edge of the path. A covering tree is defined analogously. Let π(n) be the minimum number such that every set of n points in the plane can be covered by a noncrossing path with at most π(n) edges. Let τ(n) be the analogous number for noncrossing covering trees. Dumitrescu, Gerbner, Keszegh, and Tóth (Discrete & Computational Geometry, 2014) established the following inequalities: 5n/9 - O(1) < π(n) < (1-1/601080391)n, and 9n/17 - O(1) < τ(n) ⩽ ⌊5n/6⌋. We report the following improved upper bounds: π(n) ⩽ (1-1/22)n, and τ(n) ⩽ ⌈4n/5⌉.
In the same context we study rainbow polygons. For a set of colored points in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color in its interior or on its boundary. Let ρ(k) be the minimum number such that every k-colored point set in the plane admits a perfect rainbow polygon of size ρ(k). Flores-Peñaloza, Kano, Martínez-Sandoval, Orden, Tejel, Tóth, Urrutia, and Vogtenhuber (Discrete Mathematics, 2021) proved that 20k/19 - O(1) < ρ(k) < 10k/7 + O(1). We report the improved upper bound of ρ(k) < 7k/5 + O(1).
To obtain the improved bounds we present simple O(nlog n)-time algorithms that achieve paths, trees, and polygons with our desired number of edges.
Cite as
Ahmad Biniaz. Improved Bounds for Covering Paths and Trees in the Plane. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{biniaz:LIPIcs.SoCG.2023.19,
author = {Biniaz, Ahmad},
title = {{Improved Bounds for Covering Paths and Trees in the Plane}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {19:1--19: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.19},
URN = {urn:nbn:de:0030-drops-178696},
doi = {10.4230/LIPIcs.SoCG.2023.19},
annote = {Keywords: planar point sets, covering paths, covering trees, rainbow polygons}
}
Document
Sparse Higher Order Čech Filtrations
Abstract
For a finite set of balls of radius r, the k-fold cover is the space covered by at least k balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the k-fold filtration of the centers. For k = 1, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger k, it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the k-fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case k = 1, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points.
Cite as
Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber. Sparse Higher Order Čech Filtrations. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{buchet_et_al:LIPIcs.SoCG.2023.20,
author = {Buchet, Micka\"{e}l and B. Dornelas, Bianca and Kerber, Michael},
title = {{Sparse Higher Order \v{C}ech Filtrations}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {20:1--20:17},
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.20},
URN = {urn:nbn:de:0030-drops-178709},
doi = {10.4230/LIPIcs.SoCG.2023.20},
annote = {Keywords: Sparsification, k-fold cover, Higher order \v{C}ech complexes}
}
Document
Finding Large Counterexamples by Selectively Exploring the Pachner Graph
Abstract
We often rely on censuses of triangulations to guide our intuition in 3-manifold topology. However, this can lead to misplaced faith in conjectures if the smallest counterexamples are too large to appear in our census. Since the number of triangulations increases super-exponentially with size, there is no way to expand a census beyond relatively small triangulations - the current census only goes up to 10 tetrahedra. Here, we show that it is feasible to search for large and hard-to-find counterexamples by using heuristics to selectively (rather than exhaustively) enumerate triangulations. We use this idea to find counterexamples to three conjectures which ask, for certain 3-manifolds, whether one-vertex triangulations always have a "distinctive" edge that would allow us to recognise the 3-manifold.
Cite as
Benjamin A. Burton and Alexander He. Finding Large Counterexamples by Selectively Exploring the Pachner Graph. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{burton_et_al:LIPIcs.SoCG.2023.21,
author = {Burton, Benjamin A. and He, Alexander},
title = {{Finding Large Counterexamples by Selectively Exploring the Pachner Graph}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {21:1--21: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.21},
URN = {urn:nbn:de:0030-drops-178712},
doi = {10.4230/LIPIcs.SoCG.2023.21},
annote = {Keywords: Computational topology, 3-manifolds, Triangulations, Counterexamples, Heuristics, Implementation, Pachner moves, Bistellar flips}
}
Document
Improved Algebraic Degeneracy Testing
Abstract
In the classical linear degeneracy testing problem, we are given n real numbers and a k-variate linear polynomial F, for some constant k, and have to determine whether there exist k numbers a_1,…,a_k from the set such that F(a_1,…,a_k) = 0. We consider a generalization of this problem in which F is an arbitrary constant-degree polynomial, we are given k sets of n real numbers, and have to determine whether there exists a k-tuple of numbers, one in each set, on which F vanishes. We give the first improvement over the naïve O^*(n^{k-1}) algorithm for this problem (where the O^*(⋅) notation omits subpolynomial factors).
We show that the problem can be solved in time O^*(n^{k - 2 + 4/(k+2)}) for even k and in time O^*(n^{k - 2 + (4k-8)/(k²-5)}) for odd k in the real RAM model of computation. We also prove that for k = 4, the problem can be solved in time O^*(n^2.625) in the algebraic decision tree model, and for k = 5 it can be solved in time O^*(n^3.56) in the same model, both improving on the above uniform bounds.
All our results rely on an algebraic generalization of the standard meet-in-the-middle algorithm for k-SUM, powered by recent algorithmic advances in the polynomial method for semi-algebraic range searching. In fact, our main technical result is much more broadly applicable, as it provides a general tool for detecting incidences and other interactions between points and algebraic surfaces in any dimension. In particular, it yields an efficient algorithm for a general, algebraic version of Hopcroft’s point-line incidence detection problem in any dimension.
Cite as
Jean Cardinal and Micha Sharir. Improved Algebraic Degeneracy Testing. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{cardinal_et_al:LIPIcs.SoCG.2023.22,
author = {Cardinal, Jean and Sharir, Micha},
title = {{Improved Algebraic Degeneracy Testing}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {22:1--22: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.22},
URN = {urn:nbn:de:0030-drops-178723},
doi = {10.4230/LIPIcs.SoCG.2023.22},
annote = {Keywords: Degeneracy testing, k-SUM problem, incidence bounds, Hocroft’s problem, polynomial method, algebraic decision trees}
}
Document
Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size
Abstract
In SoCG 2022, Conroy and Tóth presented several constructions of sparse, low-hop spanners in geometric intersection graphs, including an O(nlog n)-size 3-hop spanner for n disks (or fat convex objects) in the plane, and an O(nlog² n)-size 3-hop spanner for n axis-aligned rectangles in the plane. Their work left open two major questions: (i) can the size be made closer to linear by allowing larger constant stretch? and (ii) can near-linear size be achieved for more general classes of intersection graphs?
We address both questions simultaneously, by presenting new constructions of constant-hop spanners that have almost linear size and that hold for a much larger class of intersection graphs. More precisely, we prove the existence of an O(1)-hop spanner for arbitrary string graphs with O(nα_k(n)) size for any constant k, where α_k(n) denotes the k-th function in the inverse Ackermann hierarchy. We similarly prove the existence of an O(1)-hop spanner for intersection graphs of d-dimensional fat objects with O(nα_k(n)) size for any constant k and d.
We also improve on some of Conroy and Tóth’s specific previous results, in either the number of hops or the size: we describe an O(nlog n)-size 2-hop spanner for disks (or more generally objects with linear union complexity) in the plane, and an O(nlog n)-size 3-hop spanner for axis-aligned rectangles in the plane.
Our proofs are all simple, using separator theorems, recursion, shifted quadtrees, and shallow cuttings.
Cite as
Timothy M. Chan and Zhengcheng Huang. Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{chan_et_al:LIPIcs.SoCG.2023.23,
author = {Chan, Timothy M. and Huang, Zhengcheng},
title = {{Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {23:1--23: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.23},
URN = {urn:nbn:de:0030-drops-178738},
doi = {10.4230/LIPIcs.SoCG.2023.23},
annote = {Keywords: Hop spanners, geometric intersection graphs, string graphs, fat objects, separators, shallow cuttings}
}
Document
Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem
Abstract
We present a (combinatorial) algorithm with running time close to O(n^d) for computing the minimum directed L_∞ Hausdorff distance between two sets of n points under translations in any constant dimension d. This substantially improves the best previous time bound near O(n^{5d/4}) by Chew, Dor, Efrat, and Kedem from more than twenty years ago. Our solution is obtained by a new generalization of Chan’s algorithm [FOCS'13] for Klee’s measure problem.
To complement this algorithmic result, we also prove a nearly matching conditional lower bound close to Ω(n^d) for combinatorial algorithms, under the Combinatorial k-Clique Hypothesis.
Cite as
Timothy M. Chan. Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{chan:LIPIcs.SoCG.2023.24,
author = {Chan, Timothy M.},
title = {{Minimum L\underline∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {24:1--24:13},
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.24},
URN = {urn:nbn:de:0030-drops-178741},
doi = {10.4230/LIPIcs.SoCG.2023.24},
annote = {Keywords: Hausdorff distance, geometric optimization, Klee’s measure problem, fine-grained complexity}
}
Document
Meta-Diagrams for 2-Parameter Persistence
Abstract
We first introduce the notion of meta-rank for a 2-parameter persistence module, an invariant that captures the information behind images of morphisms between 1D slices of the module. We then define the meta-diagram of a 2-parameter persistence module to be the Möbius inversion of the meta-rank, resulting in a function that takes values from signed 1-parameter persistence modules. We show that the meta-rank and meta-diagram contain information equivalent to the rank invariant and the signed barcode. This equivalence leads to computational benefits, as we introduce an algorithm for computing the meta-rank and meta-diagram of a 2-parameter module M indexed by a bifiltration of n simplices in O(n³) time. This implies an improvement upon the existing algorithm for computing the signed barcode, which has O(n⁴) time complexity. This also allows us to improve the existing upper bound on the number of rectangles in the rank decomposition of M from O(n⁴) to O(n³). In addition, we define notions of erosion distance between meta-ranks and between meta-diagrams, and show that under these distances, meta-ranks and meta-diagrams are stable with respect to the interleaving distance. Lastly, the meta-diagram can be visualized in an intuitive fashion as a persistence diagram of diagrams, which generalizes the well-understood persistence diagram in the 1-parameter setting.
Cite as
Nate Clause, Tamal K. Dey, Facundo Mémoli, and Bei Wang. Meta-Diagrams for 2-Parameter Persistence. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{clause_et_al:LIPIcs.SoCG.2023.25,
author = {Clause, Nate and Dey, Tamal K. and M\'{e}moli, Facundo and Wang, Bei},
title = {{Meta-Diagrams for 2-Parameter Persistence}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {25:1--25: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.25},
URN = {urn:nbn:de:0030-drops-178754},
doi = {10.4230/LIPIcs.SoCG.2023.25},
annote = {Keywords: Multiparameter persistence modules, persistent homology, M\"{o}bius inversion, barcodes, computational topology, topological data analysis}
}
Document
Algorithms for Length Spectra of Combinatorial Tori
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
Computing a Dirichlet Domain for a Hyperbolic Surface
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-dev.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
The Parameterized Complexity of Coordinated Motion Planning
Abstract
In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n²-1)-puzzle as a special case.
In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids.
Cite as
Eduard Eiben, Robert Ganian, and Iyad Kanj. The Parameterized Complexity of Coordinated Motion Planning. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{eiben_et_al:LIPIcs.SoCG.2023.28,
author = {Eiben, Eduard and Ganian, Robert and Kanj, Iyad},
title = {{The Parameterized Complexity of Coordinated Motion Planning}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {28:1--28: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.28},
URN = {urn:nbn:de:0030-drops-178784},
doi = {10.4230/LIPIcs.SoCG.2023.28},
annote = {Keywords: coordinated motion planning, multi-agent path finding, parameterized complexity, disjoint paths on grids}
}
Document
Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
Abstract
We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers.
Cite as
David Eppstein. Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{eppstein:LIPIcs.SoCG.2023.29,
author = {Eppstein, David},
title = {{Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {29:1--29: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.29},
URN = {urn:nbn:de:0030-drops-178790},
doi = {10.4230/LIPIcs.SoCG.2023.29},
annote = {Keywords: polygonalization, non-crossing structures, output-sensitive algorithms}
}
Document
Finding a Maximum Clique in a Disk Graph
Abstract
A disk graph is an intersection graph of disks in the Euclidean plane, where the disks correspond to the vertices of the graph and a pair of vertices are adjacent if and only if their corresponding disks intersect. The problem of determining the time complexity of computing a maximum clique in a disk graph is a long-standing open question that has been very well studied in the literature. The problem is known to be open even when the radii of all the disks are in the interval [1,(1+ε)], where ε > 0. If all the disks are unit disks then there exists an O(n³log n)-time algorithm to compute a maximum clique, which is the best-known running time for over a decade. Although the problem of computing a maximum clique in a disk graph remains open, it is known to be APX-hard for the intersection graphs of many other convex objects such as intersection graphs of ellipses, triangles, and a combination of unit disks and axis-parallel rectangles. Here we obtain the following results.
- We give an algorithm to compute a maximum clique in a unit disk graph in O(n^2.5 log n)-time, which improves the previously best known running time of O(n³log n) [Eppstein '09].
- We extend a widely used "co-2-subdivision approach" to prove that computing a maximum clique in a combination of unit disks and axis-parallel rectangles is NP-hard to approximate within 4448/4449 ≈ 0.9997. The use of a "co-2-subdivision approach" was previously thought to be unlikely in this setting [Bonnet et al. '20]. Our result improves the previously known inapproximability factor of 7633010347/7633010348 ≈ 0.9999.
- We show that the parameter minimum lens width of the disk arrangement may be used to make progress in the case when disk radii are in [1,(1+ε)]. For example, if the minimum lens width is at least 0.265 and ε ≤ 0.0001, which still allows for non-Helly triples in the arrangement, then one can find a maximum clique in polynomial time.
Cite as
Jared Espenant, J. Mark Keil, and Debajyoti Mondal. Finding a Maximum Clique in a Disk Graph. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{espenant_et_al:LIPIcs.SoCG.2023.30,
author = {Espenant, Jared and Keil, J. Mark and Mondal, Debajyoti},
title = {{Finding a Maximum Clique in a Disk Graph}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {30:1--30:17},
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.30},
URN = {urn:nbn:de:0030-drops-178803},
doi = {10.4230/LIPIcs.SoCG.2023.30},
annote = {Keywords: Maximum clique, Disk graph, Time complexity, APX-hardness}
}
Document
Linear Size Universal Point Sets for Classes of Planar Graphs
Abstract
A finite set P of points in the plane is n-universal with respect to a class 𝒞 of planar graphs if every n-vertex graph in 𝒞 admits a crossing-free straight-line drawing with vertices at points of P.
For the class of all planar graphs the best known upper bound on the size of a universal point set is quadratic and the best known lower bound is linear in n.
Some classes of planar graphs are known to admit universal point sets of near linear size, however, there are no truly linear bounds for interesting classes beyond outerplanar graphs.
In this paper, we show that there is a universal point set of size 2n-2 for the class of bipartite planar graphs with n vertices. The same point set is also universal for the class of n-vertex planar graphs of maximum degree 3. The point set used for the results is what we call an exploding double chain, and we prove that this point set allows planar straight-line embeddings of many more planar graphs, namely of all subgraphs of planar graphs admitting a one-sided Hamiltonian cycle.
The result for bipartite graphs also implies that every n-vertex plane graph has a 1-bend drawing all whose bends and vertices are contained in a specific point set of size 4n-6, this improves a bound of 6n-10 for the same problem by Löffler and Tóth.
Cite as
Stefan Felsner, Hendrik Schrezenmaier, Felix Schröder, and Raphael Steiner. Linear Size Universal Point Sets for Classes of Planar Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{felsner_et_al:LIPIcs.SoCG.2023.31,
author = {Felsner, Stefan and Schrezenmaier, Hendrik and Schr\"{o}der, Felix and Steiner, Raphael},
title = {{Linear Size Universal Point Sets for Classes of Planar Graphs}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {31:1--31: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.31},
URN = {urn:nbn:de:0030-drops-178814},
doi = {10.4230/LIPIcs.SoCG.2023.31},
annote = {Keywords: Graph drawing, Universal point set, One-sided Hamiltonian, 2-page book embedding, Separating decomposition, Quadrangulation, 2-tree, Subcubic planar graph}
}
Document
When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques
Abstract
We consider ternary disc packings of the plane, i.e. the packings using discs of three different radii. Packings in which each "hole" is bounded by three pairwise tangent discs are called triangulated. Connelly conjectured that when such packings exist, one of them maximizes the proportion of the covered surface: this holds for unary and binary disc packings. For ternary packings, there are 164 pairs (r, s), 1 > r > s, allowing triangulated packings by discs of radii 1, r and s. In this paper, we enhance existing methods of dealing with maximal-density packings in order to study ternary triangulated packings. We prove that the conjecture holds for 31 triplets of disc radii and disprove it for 40 other triplets. Finally, we classify the remaining cases where our methods are not applicable. Our approach is based on the ideas present in the Hales' proof of the Kepler conjecture. Notably, our proof features local density redistribution based on computer search and interval arithmetic.
Cite as
Thomas Fernique and Daria Pchelina. When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{fernique_et_al:LIPIcs.SoCG.2023.32,
author = {Fernique, Thomas and Pchelina, Daria},
title = {{When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {32:1--32:17},
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.32},
URN = {urn:nbn:de:0030-drops-178827},
doi = {10.4230/LIPIcs.SoCG.2023.32},
annote = {Keywords: Disc packing, density, interval arithmetic}
}
Document
Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings
Abstract
Chan, Har-Peled, and Jones [SICOMP 2020] developed locality-sensitive orderings (LSO) for Euclidean space. A (τ,ρ)-LSO is a collection Σ of orderings such that for every x,y ∈ ℝ^d there is an ordering σ ∈ Σ, where all the points between x and y w.r.t. σ are in the ρ-neighborhood of either x or y. In essence, LSO allow one to reduce problems to the 1-dimensional line. Later, Filtser and Le [STOC 2022] developed LSO’s for doubling metrics, general metric spaces, and minor free graphs.
For Euclidean and doubling spaces, the number of orderings in the LSO is exponential in the dimension, which made them mainly useful for the low dimensional regime. In this paper, we develop new LSO’s for Euclidean, 𝓁_p, and doubling spaces that allow us to trade larger stretch for a much smaller number of orderings. We then use our new LSO’s (as well as the previous ones) to construct path reporting low hop spanners, fault tolerant spanners, reliable spanners, and light spanners for different metric spaces.
While many nearest neighbor search (NNS) data structures were constructed for metric spaces with implicit distance representations (where the distance between two metric points can be computed using their names, e.g. Euclidean space), for other spaces almost nothing is known. In this paper we initiate the study of the labeled NNS problem, where one is allowed to artificially assign labels (short names) to metric points. We use LSO’s to construct efficient labeled NNS data structures in this model.
Cite as
Arnold Filtser. Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{filtser:LIPIcs.SoCG.2023.33,
author = {Filtser, Arnold},
title = {{Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {33:1--33:18},
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.33},
URN = {urn:nbn:de:0030-drops-178839},
doi = {10.4230/LIPIcs.SoCG.2023.33},
annote = {Keywords: Locality sensitive ordering, nearest neighbor search, high dimensional Euclidean space, doubling dimension, planar and minor free graphs, path reporting low hop spanner, fault tolerant spanner, reliable spanner, light spanner}
}
Document
Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
Abstract
We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth.
Cite as
Esther Galby, Andrea Munaro, and Shizhou Yang. Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{galby_et_al:LIPIcs.SoCG.2023.34,
author = {Galby, Esther and Munaro, Andrea and Yang, Shizhou},
title = {{Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {34:1--34: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.34},
URN = {urn:nbn:de:0030-drops-178840},
doi = {10.4230/LIPIcs.SoCG.2023.34},
annote = {Keywords: Independent packings, intersection graphs, polynomial-time approximation schemes, tree-independence number}
}
Document
Voronoi Diagrams in the Hilbert Metric
Abstract
The Hilbert metric is a distance function defined for points lying within a convex body. It generalizes the Cayley-Klein model of hyperbolic geometry to any convex set, and it has numerous applications in the analysis and processing of convex bodies. In this paper, we study the geometric and combinatorial properties of the Voronoi diagram of a set of point sites under the Hilbert metric. Given any m-sided convex polygon Ω in the plane, we present two randomized incremental algorithms and one deterministic algorithm. The first randomized algorithm and the deterministic algorithm compute the Voronoi diagram of a set of n point sites. The second randomized algorithm extends this to compute the Voronoi diagram of the set of n sites, each of which may be a point or a line segment. Our algorithms all run in expected time O(m n log n). The algorithms use O(m n) storage, which matches the worst-case combinatorial complexity of the Voronoi diagram in the Hilbert metric.
Cite as
Auguste H. Gezalyan and David M. Mount. Voronoi Diagrams in the Hilbert Metric. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{gezalyan_et_al:LIPIcs.SoCG.2023.35,
author = {Gezalyan, Auguste H. and Mount, David M.},
title = {{Voronoi Diagrams in the Hilbert Metric}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {35:1--35: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.35},
URN = {urn:nbn:de:0030-drops-178851},
doi = {10.4230/LIPIcs.SoCG.2023.35},
annote = {Keywords: Voronoi diagrams, Hilbert metric, convexity, randomized algorithms}
}
Document
Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee’s Measure Problem and Related Problems in Dimensions d ≥ 4
Abstract
Klee’s measure problem (computing the volume of the union of n axis-parallel boxes in ℝ^d) is well known to have n^{d/2± o(1)}-time algorithms (Overmars, Yap, SICOMP'91; Chan FOCS'13). Only recently, a conditional lower bound (without any restriction to "combinatorial" algorithms) could be shown for d = 3 (Künnemann, FOCS'22). Can this result be extended to a tight lower bound for dimensions d ≥ 4?
In this paper, we formalize the technique of the tight lower bound for d = 3 using a combinatorial object we call prefix covering design. We show that these designs, which are related in spirit to combinatorial designs, directly translate to conditional lower bounds for Klee’s measure problem and various related problems. By devising good prefix covering designs, we give the following lower bounds for Klee’s measure problem in ℝ^d, the depth problem for axis-parallel boxes in ℝ^d, the largest-volume/max-perimeter empty (anchored) box problem in ℝ^{2d}, and related problems:
- Ω(n^1.90476) for d = 4,
- Ω(n^2.22222) for d = 5,
- Ω(n^{d/3 + 2√d/9-o(√d)}) for general d, assuming the 3-uniform hyperclique hypothesis. For Klee’s measure problem and the depth problem, these bounds improve previous lower bounds of Ω(n^{1.777...}), Ω(n^{2.0833...}) and Ω(n^{d/3 + 1/3 + Θ(1/d)}) respectively.
Our improved prefix covering designs were obtained by (1) exploiting a computer-aided search using problem-specific insights as well as SAT solvers, and (2) showing how to transform combinatorial covering designs known in the literature to strong prefix covering designs. In contrast, we show that our lower bounds are close to best possible using this proof technique.
Cite as
Egor Gorbachev and Marvin Künnemann. Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee’s Measure Problem and Related Problems in Dimensions d ≥ 4. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{gorbachev_et_al:LIPIcs.SoCG.2023.36,
author = {Gorbachev, Egor and K\"{u}nnemann, Marvin},
title = {{Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee’s Measure Problem and Related Problems in Dimensions d ≥ 4}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {36:1--36:14},
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.36},
URN = {urn:nbn:de:0030-drops-178861},
doi = {10.4230/LIPIcs.SoCG.2023.36},
annote = {Keywords: Fine-grained complexity theory, non-combinatorial lower bounds, computational geometry, clique detection}
}
Document
A Generalization of the Persistent Laplacian to Simplicial Maps
Abstract
The (combinatorial) graph Laplacian is a fundamental object in the analysis of, and optimization on, graphs. Via a topological view, this operator can be extended to a simplicial complex K and therefore offers a way to perform "signal processing" on p-(co)chains of K. Recently, the concept of persistent Laplacian was proposed and studied for a pair of simplicial complexes K ↪ L connected by an inclusion relation, further broadening the use of Laplace-based operators.
In this paper, we significantly expand the scope of the persistent Laplacian by generalizing it to a pair of weighted simplicial complexes connected by a weight preserving simplicial map f: K → L. Such a simplicial map setting arises frequently, e.g., when relating a coarsened simplicial representation with an original representation, or the case when the two simplicial complexes are spanned by different point sets, i.e. cases in which it does not hold that K ⊂ L. However, the simplicial map setting is much more challenging than the inclusion setting since the underlying algebraic structure is much more complicated.
We present a natural generalization of the persistent Laplacian to the simplicial setting. To shed insight on the structure behind it, as well as to develop an algorithm to compute it, we exploit the relationship between the persistent Laplacian and the Schur complement of a matrix. A critical step is to view the Schur complement as a functorial way of restricting a self-adjoint positive semi-definite operator to a given subspace. As a consequence of this relation, we prove that the qth persistent Betti number of the simplicial map f: K → L equals the nullity of the qth persistent Laplacian Δ_q^{K,L}. We then propose an algorithm for finding the matrix representation of Δ_q^{K,L} which in turn yields a fundamentally different algorithm for computing the qth persistent Betti number of a simplicial map. Finally, we study the persistent Laplacian on simplicial towers under weight-preserving simplicial maps and establish monotonicity results for their eigenvalues.
Cite as
Aziz Burak Gülen, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. A Generalization of the Persistent Laplacian to Simplicial Maps. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{gulen_et_al:LIPIcs.SoCG.2023.37,
author = {G\"{u}len, Aziz Burak and M\'{e}moli, Facundo and Wan, Zhengchao and Wang, Yusu},
title = {{A Generalization of the Persistent Laplacian to Simplicial Maps}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {37:1--37:17},
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.37},
URN = {urn:nbn:de:0030-drops-178877},
doi = {10.4230/LIPIcs.SoCG.2023.37},
annote = {Keywords: combinatorial Laplacian, persistent Laplacian, Schur complement, persistent homology, persistent Betti number}
}
Document
The Christoffel-Darboux Kernel for Topological Data Analysis
Abstract
Persistent homology has been widely used to study the topology of point clouds in ℝⁿ. Standard approaches are very sensitive to outliers, and their computational complexity depends badly on the number of data points. In this paper we introduce a novel persistence module for a point cloud using the theory of Christoffel-Darboux kernels. This module is robust to (statistical) outliers in the data, and can be computed in time linear in the number of data points. We illustrate the benefits and limitations of our new module with various numerical examples in ℝⁿ, for n = 1, 2, 3. Our work expands upon recent applications of Christoffel-Darboux kernels in the context of statistical data analysis and geometric inference [Lasserre et al., 2022]. There, these kernels are used to construct a polynomial whose level sets capture the geometry of a point cloud in a precise sense. We show that the persistent homology associated to the sublevel set filtration of this polynomial is stable with respect to the Wasserstein distance. Moreover, we show that the persistent homology of this filtration can be computed in singly exponential time in the ambient dimension n, using a recent algorithm of Basu & Karisani [Basu and Karisani, 2022].
Cite as
Pepijn Roos Hoefgeest and Lucas Slot. The Christoffel-Darboux Kernel for Topological Data Analysis. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{rooshoefgeest_et_al:LIPIcs.SoCG.2023.38,
author = {Roos Hoefgeest, Pepijn and Slot, Lucas},
title = {{The Christoffel-Darboux Kernel for Topological Data Analysis}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {38:1--38:20},
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.38},
URN = {urn:nbn:de:0030-drops-178889},
doi = {10.4230/LIPIcs.SoCG.2023.38},
annote = {Keywords: Topological Data Analysis, Geometric Inference, Christoffel-Darboux Kernels, Persistent Homology, Wasserstein Distance, Semi-Algebraic Sets}
}
Document
The Number of Edges in Maximal 2-Planar Graphs
Abstract
A graph is 2-planar if it has local crossing number two, that is, it can be drawn in the plane such that every edge has at most two crossings. A graph is maximal 2-planar if no edge can be added such that the resulting graph remains 2-planar. A 2-planar graph on n vertices has at most 5n-10 edges, and some (maximal) 2-planar graphs - referred to as optimal 2-planar - achieve this bound. However, in strong contrast to maximal planar graphs, a maximal 2-planar graph may have fewer than the maximum possible number of edges. In this paper, we determine the minimum edge density of maximal 2-planar graphs by proving that every maximal 2-planar graph on n ≥ 5 vertices has at least 2n edges. We also show that this bound is tight, up to an additive constant. The lower bound is based on an analysis of the degree distribution in specific classes of drawings of the graph. The upper bound construction is verified by carefully exploring the space of admissible drawings using computer support.
Cite as
Michael Hoffmann and Meghana M. Reddy. The Number of Edges in Maximal 2-Planar Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{hoffmann_et_al:LIPIcs.SoCG.2023.39,
author = {Hoffmann, Michael and M. Reddy, Meghana},
title = {{The Number of Edges in Maximal 2-Planar Graphs}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {39:1--39: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.39},
URN = {urn:nbn:de:0030-drops-178894},
doi = {10.4230/LIPIcs.SoCG.2023.39},
annote = {Keywords: k-planar graphs, local crossing number, saturated graphs, beyond-planar graphs}
}
Document
Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings
Abstract
We study dynamic planar graphs with n vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We dynamically maintain a combinatorial embedding of such a planar graph, subject to connectivity and 2-vertex-connectivity (biconnectivity) queries between pairs of vertices. Whenever a query pair is connected and not biconnected, we find the first and last cutvertex separating them.
Additionally, we allow local changes to the embedding by flipping the embedding of a subgraph that is connected by at most two vertices to the rest of the graph.
We support all queries and updates in deterministic, worst-case, O(log² n) time, using an O(n)-sized data structure.
Cite as
Jacob Holm, Ivor van der Hoog, and Eva Rotenberg. Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{holm_et_al:LIPIcs.SoCG.2023.40,
author = {Holm, Jacob and van der Hoog, Ivor and Rotenberg, Eva},
title = {{Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {40:1--40:18},
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.40},
URN = {urn:nbn:de:0030-drops-178909},
doi = {10.4230/LIPIcs.SoCG.2023.40},
annote = {Keywords: dynamic graphs, planarity, connectivity}
}
Document
Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems
Abstract
Given a complete simple topological graph G, a k-face generated by G is the open bounded region enclosed by the edges of a non-self-intersecting k-cycle in G. Interestingly, there are complete simple topological graphs with the property that every odd face it generates contains the origin. In this paper, we show that every complete n-vertex simple topological graph generates at least Ω(n^{1/3}) pairwise disjoint 4-faces. As an immediate corollary, every complete simple topological graph on n vertices drawn in the unit square generates a 4-face with area at most O(n^{-1/3}). Finally, we investigate a ℤ₂ variant of Heilbronn’s triangle problem for not necessarily simple complete topological graphs.
Cite as
Alfredo Hubard and Andrew Suk. Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{hubard_et_al:LIPIcs.SoCG.2023.41,
author = {Hubard, Alfredo and Suk, Andrew},
title = {{Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {41:1--41: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.41},
URN = {urn:nbn:de:0030-drops-178917},
doi = {10.4230/LIPIcs.SoCG.2023.41},
annote = {Keywords: Disjoint faces, simple topological graphs, topological Heilbronn problems}
}
Document
On the Width of Complicated JSJ Decompositions
Abstract
Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a "sufficiently complicated" JSJ decomposition of a 3-manifold enforces a "complicated structure" for all of its triangulations. More concretely, we show that, under certain conditions, the treewidth (resp. pathwidth) of the graph that captures the incidences between the pieces of the JSJ decomposition of an irreducible, closed, orientable 3-manifold M yields a linear lower bound on its treewidth tw (M) (resp. pathwidth pw(M)), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of M.
We present several applications of this result. We give the first example of an infinite family of bounded-treewidth 3-manifolds with unbounded pathwidth. We construct Haken 3-manifolds with arbitrarily large treewidth - previously the existence of such 3-manifolds was only known in the non-Haken case. We also show that the problem of providing a constant-factor approximation for the treewidth (resp. pathwidth) of bounded-degree graphs efficiently reduces to computing a constant-factor approximation for the treewidth (resp. pathwidth) of 3-manifolds.
Cite as
Kristóf Huszár and Jonathan Spreer. On the Width of Complicated JSJ Decompositions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{huszar_et_al:LIPIcs.SoCG.2023.42,
author = {Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan},
title = {{On the Width of Complicated JSJ Decompositions}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {42:1--42:18},
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.42},
URN = {urn:nbn:de:0030-drops-178920},
doi = {10.4230/LIPIcs.SoCG.2023.42},
annote = {Keywords: computational 3-manifold topology, fixed-parameter tractability, generalized Heegaard splittings, JSJ decompositions, pathwidth, treewidth, triangulations}
}
Document
Reconfiguration of Colorings in Triangulations of the Sphere
Abstract
In 1973, Fisk proved that any 4-coloring of a 3-colorable triangulation of the 2-sphere can be obtained from any 3-coloring by a sequence of Kempe-changes. On the other hand, in the case where we are only allowed to recolor a single vertex in each step, which is a special case of a Kempe-change, there exists a 4-coloring that cannot be obtained from any 3-coloring.
In this paper, we present a linear-time checkable characterization of a 4-coloring of a 3-colorable triangulation of the 2-sphere that can be obtained from a 3-coloring by a sequence of recoloring operations at single vertices. In addition, we develop a quadratic-time algorithm to find such a recoloring sequence if it exists; our proof implies that we can always obtain a quadratic length recoloring sequence. We also present a linear-time checkable criterion for a 3-colorable triangulation of the 2-sphere that all 4-colorings can be obtained from a 3-coloring by such a sequence. Moreover, we consider a high-dimensional setting. As a natural generalization of our first result, we obtain a polynomial-time checkable characterization of a k-coloring of a (k-1)-colorable triangulation of the (k-2)-sphere that can be obtained from a (k-1)-coloring by a sequence of recoloring operations at single vertices and the corresponding algorithmic result. Furthermore, we show that the problem of deciding whether, for given two (k+1)-colorings of a (k-1)-colorable triangulation of the (k-2)-sphere, one can be obtained from the other by such a sequence is PSPACE-complete for any fixed k ≥ 4. Our results above can be rephrased as new results on the computational problems named k-Recoloring and Connectedness of k-Coloring Reconfiguration Graph, which are fundamental problems in the field of combinatorial reconfiguration.
Cite as
Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Reconfiguration of Colorings in Triangulations of the Sphere. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{ito_et_al:LIPIcs.SoCG.2023.43,
author = {Ito, Takehiro and Iwamasa, Yuni and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio and Ozeki, Kenta},
title = {{Reconfiguration of Colorings in Triangulations of the Sphere}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {43:1--43: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.43},
URN = {urn:nbn:de:0030-drops-178936},
doi = {10.4230/LIPIcs.SoCG.2023.43},
annote = {Keywords: Graph coloring, Triangulation of the sphere, Combinatorial reconfiguration}
}
Document
On the Geometric Thickness of 2-Degenerate Graphs
Abstract
A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomposes into 4 plane forests. Therefore, the geometric arboricity, and hence the geometric thickness, of 2-degenerate graphs is at most 4. On the other hand, we show that there are 2-degenerate graphs that do not admit any straight-line drawing with a decomposition of the edge set into 2 plane graphs. That is, there are 2-degenerate graphs with geometric thickness, and hence geometric arboricity, at least 3. This answers two questions posed by Eppstein [Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004].
Cite as
Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz. On the Geometric Thickness of 2-Degenerate Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{jain_et_al:LIPIcs.SoCG.2023.44,
author = {Jain, Rahul and Ricci, Marco and Rollin, Jonathan and Schulz, Andr\'{e}},
title = {{On the Geometric Thickness of 2-Degenerate Graphs}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {44:1--44: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.44},
URN = {urn:nbn:de:0030-drops-178946},
doi = {10.4230/LIPIcs.SoCG.2023.44},
annote = {Keywords: Degeneracy, geometric thickness, geometric arboricity}
}
Document
The Localized Union-Of-Balls Bifiltration
Abstract
We propose an extension of the classical union-of-balls filtration of persistent homology: fixing a point q, we focus our attention to a ball centered at q whose radius is controlled by a second scale parameter. We discuss an absolute variant, where the union is just restricted to the q-ball, and a relative variant where the homology of the q-ball relative to its boundary is considered. Interestingly, these natural constructions lead to bifiltered simplicial complexes which are not k-critical for any finite k. Nevertheless, we demonstrate that these bifiltrations can be computed exactly and efficiently, and we provide a prototypical implementation using the CGAL library. We also argue that some of the recent algorithmic advances for 2-parameter persistence (which usually assume k-criticality for some finite k) carry over to the ∞-critical case.
Cite as
Michael Kerber and Matthias Söls. The Localized Union-Of-Balls Bifiltration. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{kerber_et_al:LIPIcs.SoCG.2023.45,
author = {Kerber, Michael and S\"{o}ls, Matthias},
title = {{The Localized Union-Of-Balls Bifiltration}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {45:1--45:19},
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.45},
URN = {urn:nbn:de:0030-drops-178953},
doi = {10.4230/LIPIcs.SoCG.2023.45},
annote = {Keywords: Topological Data Analysis, Multi-Parameter Persistence, Persistent Local Homology}
}
Document
Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set
Abstract
Set cover and hitting set are fundamental problems in combinatorial optimization which are well-studied in the offline, online, and dynamic settings. We study the geometric versions of these problems and present new online and dynamic algorithms for them. In the online version of set cover (resp. hitting set), m sets (resp. n points) are given and n points (resp. m sets) arrive online, one-by-one. In the dynamic versions, points (resp. sets) can arrive as well as depart. Our goal is to maintain a set cover (resp. hitting set), minimizing the size of the computed solution.
For online set cover for (axis-parallel) squares of arbitrary sizes, we present a tight O(log n)-competitive algorithm. In the same setting for hitting set, we provide a tight O(log N)-competitive algorithm, assuming that all points have integral coordinates in [0,N)². No online algorithm had been known for either of these settings, not even for unit squares (apart from the known online algorithms for arbitrary set systems).
For both dynamic set cover and hitting set with d-dimensional hyperrectangles, we obtain (log m)^O(d)-approximation algorithms with (log m)^O(d) worst-case update time. This partially answers an open question posed by Chan et al. [SODA'22]. Previously, no dynamic algorithms with polylogarithmic update time were known even in the setting of squares (for either of these problems). Our main technical contributions are an extended quad-tree approach and a frequency reduction technique that reduces geometric set cover instances to instances of general set cover with bounded frequency.
Cite as
Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, and Andreas Wiese. Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 46:1-46:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{khan_et_al:LIPIcs.SoCG.2023.46,
author = {Khan, Arindam and Lonkar, Aditya and Rahul, Saladi and Subramanian, Aditya and Wiese, Andreas},
title = {{Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {46:1--46:17},
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.46},
URN = {urn:nbn:de:0030-drops-178967},
doi = {10.4230/LIPIcs.SoCG.2023.46},
annote = {Keywords: Geometric Set Cover, Hitting Set, Rectangles, Squares, Hyperrectangles, Online Algorithms, Dynamic Data Structures}
}
Document
Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function
Abstract
In STOC'95 [S. Arya et al., 1995] Arya et al. showed that any set of n points in ℝ^d admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hop-diameter k with O(n α_k(n)) edges, for any k ≥ 2. The function α_k is the inverse of a certain Ackermann-style function, where α₀(n) = ⌈n/2⌉, α₁(n) = ⌈√n⌉, α₂(n) = ⌈log n⌉, α₃(n) = ⌈log log n⌉, α₄(n) = log^* n, α₅(n) = ⌊ 1/2 log^*n ⌋, …. Roughly speaking, for k ≥ 2 the function α_{k} is close to ⌊(k-2)/2⌋-iterated log-star function, i.e., log with ⌊(k-2)/2⌋ stars.
Despite a large body of work on spanners of bounded hop-diameter, the fundamental question of whether this tradeoff between size and hop-diameter of Euclidean (1+ε)-spanners is optimal has remained open, even in one-dimensional spaces. Three lower bound tradeoffs are known:
- An optimal k versus Ω(n α_k(n)) by Alon and Schieber [N. Alon and B. Schieber, 1987], but it applies to stretch 1 (not 1+ε).
- A suboptimal k versus Ω(nα_{2k+6}(n)) by Chan and Gupta [H. T.-H. Chan and A. Gupta, 2006].
- A suboptimal k versus Ω(n/(2^{6⌊k/2⌋}) α_k(n)) by Le et al. [Le et al., 2022]. This paper establishes the optimal k versus Ω(n α_k(n)) lower bound tradeoff for stretch 1+ε, for any ε > 0, and for any k. An important conceptual contribution of this work is in achieving optimality by shaving off an extremely slowly growing term, namely 2^{6⌊k/2⌋} for k ≤ O(α(n)); such a fine-grained optimization (that achieves optimality) is very rare in the literature.
To shave off the 2^{6⌊k/2⌋} term from the previous bound of Le et al., our argument has to drill much deeper. In particular, we propose a new way of analyzing recurrences that involve inverse-Ackermann style functions, and our key technical contribution is in presenting the first explicit construction of concave versions of these functions. An important advantage of our approach over previous ones is its robustness: While all previous lower bounds are applicable only to restricted 1-dimensional point sets, ours applies even to random point sets in constant-dimensional spaces.
Cite as
Hung Le, Lazar Milenković, and Shay Solomon. Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{le_et_al:LIPIcs.SoCG.2023.47,
author = {Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay},
title = {{Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {47:1--47:17},
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.47},
URN = {urn:nbn:de:0030-drops-178976},
doi = {10.4230/LIPIcs.SoCG.2023.47},
annote = {Keywords: Euclidean spanners, Ackermann functions, convex functions, hop-diameter}
}
Document
Shortest Paths in Portalgons
Abstract
Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric.
We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons.
The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons.
Cite as
Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals. Shortest Paths in Portalgons. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{loffler_et_al:LIPIcs.SoCG.2023.48,
author = {L\"{o}ffler, Maarten and Ophelders, Tim and Silveira, Rodrigo I. and Staals, Frank},
title = {{Shortest Paths in Portalgons}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {48:1--48: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.48},
URN = {urn:nbn:de:0030-drops-178980},
doi = {10.4230/LIPIcs.SoCG.2023.48},
annote = {Keywords: Polyhedral surfaces, shortest paths, geodesic distance, Delaunay triangulation}
}
Document
The Geodesic Edge Center of a Simple Polygon
Abstract
The geodesic edge center of a polygon is a point c inside the polygon that minimizes the maximum geodesic distance from c to any edge of the polygon, where geodesic distance is the shortest path distance inside the polygon. We give a linear-time algorithm to find a geodesic edge center of a simple polygon. This improves on the previous O(n log n) time algorithm by Lubiw and Naredla [European Symposium on Algorithms, 2021]. The algorithm builds on an algorithm to find the geodesic vertex center of a simple polygon due to Pollack, Sharir, and Rote [Discrete & Computational Geometry, 1989] and an improvement to linear time by Ahn, Barba, Bose, De Carufel, Korman, and Oh [Discrete & Computational Geometry, 2016].
The geodesic edge center can easily be found from the geodesic farthest-edge Voronoi diagram of the polygon. Finding that Voronoi diagram in linear time is an open question, although the geodesic nearest edge Voronoi diagram (the medial axis) can be found in linear time. As a first step of our geodesic edge center algorithm, we give a linear-time algorithm to find the geodesic farthest-edge Voronoi diagram restricted to the polygon boundary.
Cite as
Anna Lubiw and Anurag Murty Naredla. The Geodesic Edge Center of a Simple Polygon. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{lubiw_et_al:LIPIcs.SoCG.2023.49,
author = {Lubiw, Anna and Naredla, Anurag Murty},
title = {{The Geodesic Edge Center of a Simple Polygon}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {49:1--49: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.49},
URN = {urn:nbn:de:0030-drops-178994},
doi = {10.4230/LIPIcs.SoCG.2023.49},
annote = {Keywords: geodesic center of polygon, farthest edges, farthest-segment Voronoi diagram}
}
Document
A Structural Approach to Tree Decompositions of Knots and Spatial Graphs
Abstract
Knots are commonly represented and manipulated via diagrams, which are decorated planar graphs. When such a knot diagram has low treewidth, parameterized graph algorithms can be leveraged to ensure the fast computation of many invariants and properties of the knot. It was recently proved that there exist knots which do not admit any diagram of low treewidth, and the proof relied on intricate low-dimensional topology techniques. In this work, we initiate a thorough investigation of tree decompositions of knot diagrams (or more generally, diagrams of spatial graphs) using ideas from structural graph theory. We define an obstruction on spatial embeddings that forbids low tree width diagrams, and we prove that it is optimal with respect to a related width invariant. We then show the existence of this obstruction for knots of high representativity, which include for example torus knots, providing a new and self-contained proof that those do not admit diagrams of low treewidth. This last step is inspired by a result of Pardon on knot distortion.
Cite as
Corentin Lunel and Arnaud de Mesmay. A Structural Approach to Tree Decompositions of Knots and Spatial Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{lunel_et_al:LIPIcs.SoCG.2023.50,
author = {Lunel, Corentin and de Mesmay, Arnaud},
title = {{A Structural Approach to Tree Decompositions of Knots and Spatial Graphs}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {50:1--50: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.50},
URN = {urn:nbn:de:0030-drops-179002},
doi = {10.4230/LIPIcs.SoCG.2023.50},
annote = {Keywords: Knots, Spatial Graphs, Tree Decompositions, Tangle, Representativity}
}
Document
Ephemeral Persistence Features and the Stability of Filtered Chain Complexes
Abstract
We strengthen the usual stability theorem for Vietoris-Rips (VR) persistent homology of finite metric spaces by building upon constructions due to Usher and Zhang in the context of filtered chain complexes. The information present at the level of filtered chain complexes includes ephemeral points, i.e. points with zero persistence, which provide additional information to that present at homology level. The resulting invariant, called verbose barcode, which has a stronger discriminating power than the usual barcode, is proved to be stable under certain metrics which are sensitive to these ephemeral points. In some situations, we provide ways to compute such metrics between verbose barcodes. We also exhibit several examples of finite metric spaces with identical (standard) VR barcodes yet with different verbose VR barcodes thus confirming that these ephemeral points strengthen the discriminating power of the standard VR barcode.
Cite as
Facundo Mémoli and Ling Zhou. Ephemeral Persistence Features and the Stability of Filtered Chain Complexes. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{memoli_et_al:LIPIcs.SoCG.2023.51,
author = {M\'{e}moli, Facundo and Zhou, Ling},
title = {{Ephemeral Persistence Features and the Stability of Filtered Chain Complexes}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {51:1--51:18},
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.51},
URN = {urn:nbn:de:0030-drops-179014},
doi = {10.4230/LIPIcs.SoCG.2023.51},
annote = {Keywords: filtered chain complexes, Vietoris-Rips complexes, barcode, bottleneck distance, matching distance, Gromov-Hausdorff distance}
}
Document
Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications
Abstract
Any system of bisectors (in the sense of abstract Voronoi diagrams) defines an arrangement of simple curves in the plane. We define Voronoi-like graphs on such an arrangement, which are graphs whose vertices are locally Voronoi. A vertex v is called locally Voronoi, if v and its incident edges appear in the Voronoi diagram of three sites. In a so-called admissible bisector system, where Voronoi regions are connected and cover the plane, we prove that any Voronoi-like graph is indeed an abstract Voronoi diagram. The result can be seen as an abstract dual version of Delaunay’s theorem on (locally) empty circles.
Further, we define Voronoi-like cycles in an admissible bisector system, and show that the Voronoi-like graph induced by such a cycle C is a unique tree (or a forest, if C is unbounded). In the special case where C is the boundary of an abstract Voronoi region, the induced Voronoi-like graph can be computed in expected linear time following the technique of [Junginger and Papadopoulou SOCG'18]. Otherwise, within the same time, the algorithm constructs the Voronoi-like graph of a cycle C′ on the same set (or subset) of sites, which may equal C or be enclosed by C. Overall, the technique computes abstract Voronoi (or Voronoi-like) trees and forests in linear expected time, given the order of their leaves along a Voronoi-like cycle. We show a direct application in updating a constraint Delaunay triangulation in linear expected time, after the insertion of a new segment constraint, simplifying upon the result of [Shewchuk and Brown CGTA 2015].
Cite as
Evanthia Papadopoulou. Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{papadopoulou:LIPIcs.SoCG.2023.52,
author = {Papadopoulou, Evanthia},
title = {{Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {52:1--52: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.52},
URN = {urn:nbn:de:0030-drops-179024},
doi = {10.4230/LIPIcs.SoCG.2023.52},
annote = {Keywords: Voronoi-like graph, abstract Voronoi diagram, Delaunay’s theorem, Voronoi tree, linear-time randomized algorithm, constraint Delaunay triangulation}
}
Document
Random Projections for Curves in High Dimensions
Abstract
Modern time series analysis requires the ability to handle datasets that are inherently high-dimensional; examples include applications in climatology, where measurements from numerous sensors must be taken into account, or inventory tracking of large shops, where the dimension is defined by the number of tracked items. The standard way to mitigate computational issues arising from the high dimensionality of the data is by applying some dimension reduction technique that preserves the structural properties of the ambient space. The dissimilarity between two time series is often measured by "discrete" notions of distance, e.g. the dynamic time warping or the discrete Fréchet distance. Since all these distance functions are computed directly on the points of a time series, they are sensitive to different sampling rates or gaps. The continuous Fréchet distance offers a popular alternative which aims to alleviate this by taking into account all points on the polygonal curve obtained by linearly interpolating between any two consecutive points in a sequence.
We study the ability of random projections à la Johnson and Lindenstrauss to preserve the continuous Fréchet distance of polygonal curves by effectively reducing the dimension. In particular, we show that one can reduce the dimension to O(ε^{-2} log N), where N is the total number of input points while preserving the continuous Fréchet distance between any two determined polygonal curves within a factor of 1± ε. We conclude with applications on clustering.
Cite as
Ioannis Psarros and Dennis Rohde. Random Projections for Curves in High Dimensions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{psarros_et_al:LIPIcs.SoCG.2023.53,
author = {Psarros, Ioannis and Rohde, Dennis},
title = {{Random Projections for Curves in High Dimensions}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {53:1--53: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.53},
URN = {urn:nbn:de:0030-drops-179030},
doi = {10.4230/LIPIcs.SoCG.2023.53},
annote = {Keywords: polygonal curves, time series, dimension reduction, Johnson-Lindenstrauss lemma, Fr\'{e}chet distance}
}
Document
New Approximation Algorithms for Touring Regions
Abstract
We analyze the touring regions problem: find a (1+ε)-approximate Euclidean shortest path in d-dimensional space that starts at a given starting point, ends at a given ending point, and visits given regions R₁, R₂, R₃, … , R_n in that order.
Our main result is an O (n/√ε log{1/ε} + 1/ε)-time algorithm for touring disjoint disks. We also give an O(min(n/ε, n²/√ε))-time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions; we obtain O(n/{ε^{d-1}} log²1/ε + 1/ε^{2d-2}) and O(n/ε^{2d-2})-time algorithms for touring disjoint d-dimensional balls and convex fat bodies, respectively.
Cite as
Benjamin Qi and Richard Qi. New Approximation Algorithms for Touring Regions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{qi_et_al:LIPIcs.SoCG.2023.54,
author = {Qi, Benjamin and Qi, Richard},
title = {{New Approximation Algorithms for Touring Regions}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {54:1--54: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.54},
URN = {urn:nbn:de:0030-drops-179047},
doi = {10.4230/LIPIcs.SoCG.2023.54},
annote = {Keywords: shortest paths, convex bodies, fat objects, disks}
}
Document
Combinatorial Depth Measures for Hyperplane Arrangements
Abstract
Regression depth, introduced by Rousseeuw and Hubert in 1999, is a notion that measures how good of a regression hyperplane a given query hyperplane is with respect to a set of data points. Under projective duality, this can be interpreted as a depth measure for query points with respect to an arrangement of data hyperplanes. The study of depth measures for query points with respect to a set of data points has a long history, and many such depth measures have natural counterparts in the setting of hyperplane arrangements. For example, regression depth is the counterpart of Tukey depth. Motivated by this, we study general families of depth measures for hyperplane arrangements and show that all of them must have a deep point. Along the way we prove a Tverberg-type theorem for hyperplane arrangements, giving a positive answer to a conjecture by Rousseeuw and Hubert from 1999. We also get three new proofs of the centerpoint theorem for regression depth, all of which are either stronger or more general than the original proof by Amenta, Bern, Eppstein, and Teng. Finally, we prove a version of the center transversal theorem for regression depth.
Cite as
Patrick Schnider and Pablo Soberón. Combinatorial Depth Measures for Hyperplane Arrangements. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{schnider_et_al:LIPIcs.SoCG.2023.55,
author = {Schnider, Patrick and Sober\'{o}n, Pablo},
title = {{Combinatorial Depth Measures for Hyperplane Arrangements}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {55:1--55:14},
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.55},
URN = {urn:nbn:de:0030-drops-179055},
doi = {10.4230/LIPIcs.SoCG.2023.55},
annote = {Keywords: Depth measures, Hyperplane arrangements, Regression depth, Tverberg theorem}
}
Document
FibeRed: Fiberwise Dimensionality Reduction of Topologically Complex Data with Vector Bundles
Abstract
Datasets with non-trivial large scale topology can be hard to embed in low-dimensional Euclidean space with existing dimensionality reduction algorithms. We propose to model topologically complex datasets using vector bundles, in such a way that the base space accounts for the large scale topology, while the fibers account for the local geometry. This allows one to reduce the dimensionality of the fibers, while preserving the large scale topology. We formalize this point of view and, as an application, we describe a dimensionality reduction algorithm based on topological inference for vector bundles. The algorithm takes as input a dataset together with an initial representation in Euclidean space, assumed to recover part of its large scale topology, and outputs a new representation that integrates local representations obtained through local linear dimensionality reduction. We demonstrate this algorithm on examples coming from dynamical systems and chemistry. In these examples, our algorithm is able to learn topologically faithful embeddings of the data in lower target dimension than various well known metric-based dimensionality reduction algorithms.
Cite as
Luis Scoccola and Jose A. Perea. FibeRed: Fiberwise Dimensionality Reduction of Topologically Complex Data with Vector Bundles. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 56:1-56:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{scoccola_et_al:LIPIcs.SoCG.2023.56,
author = {Scoccola, Luis and Perea, Jose A.},
title = {{FibeRed: Fiberwise Dimensionality Reduction of Topologically Complex Data with Vector Bundles}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {56:1--56:18},
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.56},
URN = {urn:nbn:de:0030-drops-179068},
doi = {10.4230/LIPIcs.SoCG.2023.56},
annote = {Keywords: topological inference, dimensionality reduction, vector bundle, cocycle}
}
Document
Toroidal Coordinates: Decorrelating Circular Coordinates with Lattice Reduction
Abstract
The circular coordinates algorithm of de Silva, Morozov, and Vejdemo-Johansson takes as input a dataset together with a cohomology class representing a 1-dimensional hole in the data; the output is a map from the data into the circle that captures this hole, and that is of minimum energy in a suitable sense. However, when applied to several cohomology classes, the output circle-valued maps can be "geometrically correlated" even if the chosen cohomology classes are linearly independent. It is shown in the original work that less correlated maps can be obtained with suitable integer linear combinations of the cohomology classes, with the linear combinations being chosen by inspection. In this paper, we identify a formal notion of geometric correlation between circle-valued maps which, in the Riemannian manifold case, corresponds to the Dirichlet form, a bilinear form derived from the Dirichlet energy. We describe a systematic procedure for constructing low energy torus-valued maps on data, starting from a set of linearly independent cohomology classes. We showcase our procedure with computational examples. Our main algorithm is based on the Lenstra-Lenstra-Lovász algorithm from computational number theory.
Cite as
Luis Scoccola, Hitesh Gakhar, Johnathan Bush, Nikolas Schonsheck, Tatum Rask, Ling Zhou, and Jose A. Perea. Toroidal Coordinates: Decorrelating Circular Coordinates with Lattice Reduction. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 57:1-57:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{scoccola_et_al:LIPIcs.SoCG.2023.57,
author = {Scoccola, Luis and Gakhar, Hitesh and Bush, Johnathan and Schonsheck, Nikolas and Rask, Tatum and Zhou, Ling and Perea, Jose A.},
title = {{Toroidal Coordinates: Decorrelating Circular Coordinates with Lattice Reduction}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {57:1--57:20},
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.57},
URN = {urn:nbn:de:0030-drops-179073},
doi = {10.4230/LIPIcs.SoCG.2023.57},
annote = {Keywords: dimensionality reduction, lattice reduction, Dirichlet energy, harmonic, cocycle}
}
Document
Topological Universality of the Art Gallery Problem
Abstract
We prove that any compact semi-algebraic set is homeomorphic to the solution space of some art gallery problem. Previous works have established similar universality theorems, but holding only up to homotopy equivalence, rather than homeomorphism, and prior to this work, the existence of art galleries even for simple spaces such as the Möbius strip or the three-holed torus were unknown. Our construction relies on an elegant and versatile gadget to copy guard positions with minimal overhead. It is simpler than previous constructions, consisting of a single rectangular room with convex slits cut out from the edges. We show that both the orientable and non-orientable surfaces of genus n admit galleries with only O(n) vertices.
Cite as
Jack Stade and Jamie Tucker-Foltz. Topological Universality of the Art Gallery Problem. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{stade_et_al:LIPIcs.SoCG.2023.58,
author = {Stade, Jack and Tucker-Foltz, Jamie},
title = {{Topological Universality of the Art Gallery Problem}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {58:1--58:13},
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.58},
URN = {urn:nbn:de:0030-drops-179082},
doi = {10.4230/LIPIcs.SoCG.2023.58},
annote = {Keywords: Art gallery, Homeomorphism, Exists-R, ETR, Semi-algebraic sets, Universality}
}
Document
On Higher Dimensional Point Sets in General Position
Abstract
A finite point set in ℝ^d is in general position if no d + 1 points lie on a common hyperplane. Let α_d(N) be the largest integer such that any set of N points in ℝ^d with no d + 2 members on a common hyperplane, contains a subset of size α_d(N) in general position. Using the method of hypergraph containers, Balogh and Solymosi showed that α₂(N) < N^{5/6 + o(1)}. In this paper, we also use the container method to obtain new upper bounds for α_d(N) when d ≥ 3. More precisely, we show that if d is odd, then α_d(N) < N^{1/2 + 1/(2d) + o(1)}, and if d is even, we have α_d(N) < N^{1/2 + 1/(d-1) + o(1)}.
We also study the classical problem of determining the maximum number a(d,k,n) of points selected from the grid [n]^d such that no k + 2 members lie on a k-flat. For fixed d and k, we show that a(d,k,n)≤ O(n^{d/{2⌊(k+2)/4⌋}(1- 1/{2⌊(k+2)/4⌋d+1})}), which improves the previously best known bound of O(n^{d/⌊(k + 2)/2⌋}) due to Lefmann when k+2 is congruent to 0 or 1 mod 4.
Cite as
Andrew Suk and Ji Zeng. On Higher Dimensional Point Sets in General Position. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{suk_et_al:LIPIcs.SoCG.2023.59,
author = {Suk, Andrew and Zeng, Ji},
title = {{On Higher Dimensional Point Sets in General Position}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {59:1--59:13},
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.59},
URN = {urn:nbn:de:0030-drops-179097},
doi = {10.4230/LIPIcs.SoCG.2023.59},
annote = {Keywords: independent sets, hypergraph container method, generalised Sidon sets}
}
Document
Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data
Abstract
We focus on efficient computations of topological descriptors for voxel data. This type of data includes 2D greyscale images, 3D medical scans, but also higher-dimensional scalar fields arising from physical simulations. In recent years we have seen an increase in applications of topological methods for such data. However, computational issues remain an obstacle.
We therefore propose a streaming scheme which simplifies large 3-dimensional voxel data - while provably retaining its persistent homology. We combine this scheme with an efficient boundary matrix reduction implementation, obtaining an end-to-end tool for persistent homology of large data. Computational experiments show its state-of-the-art performance. In particular, we are now able to robustly handle complex datasets with several billions voxels on a regular laptop.
A software implementation called Cubicle is available as open-source: https://bitbucket.org/hubwag/cubicle.
Cite as
Hubert Wagner. Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{wagner:LIPIcs.SoCG.2023.60,
author = {Wagner, Hubert},
title = {{Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {60:1--60: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.60},
URN = {urn:nbn:de:0030-drops-179107},
doi = {10.4230/LIPIcs.SoCG.2023.60},
annote = {Keywords: Computational topology, topological data analysis, topological image analysis, persistent homology, persistence diagram, discrete Morse theory, algorithm engineering, implementation, voxel data, volume data, image data}
}
Document
Maximum Overlap Area of a Convex Polyhedron and a Convex Polygon Under Translation
Abstract
Let P be a convex polyhedron and Q be a convex polygon with n vertices in total in three-dimensional space. We present a deterministic algorithm that finds a translation vector v ∈ ℝ³ maximizing the overlap area |P ∩ (Q + v)| in O(n log² n) time. We then apply our algorithm to solve two related problems. We give an O(n log³ n) time algorithm that finds the maximum overlap area of three convex polygons with n vertices in total. We also give an O(n log² n) time algorithm that minimizes the symmetric difference of two convex polygons under scaling and translation.
Cite as
Honglin Zhu and Hyuk Jun Kweon. Maximum Overlap Area of a Convex Polyhedron and a Convex Polygon Under Translation. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{zhu_et_al:LIPIcs.SoCG.2023.61,
author = {Zhu, Honglin and Kweon, Hyuk Jun},
title = {{Maximum Overlap Area of a Convex Polyhedron and a Convex Polygon Under Translation}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {61:1--61: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.61},
URN = {urn:nbn:de:0030-drops-179116},
doi = {10.4230/LIPIcs.SoCG.2023.61},
annote = {Keywords: computational geometry, shape matching, arrangement}
}
Document
Media Exposition
Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition)
Abstract
We provide a skit and an applet to illustrate fractional cascading in the context of half-plane range search for points in the Euclidean plane, which takes O(log N + h) output-sensitive time. In the video, a group of news anchors struggles to find the correct data structure to efficiently send out an early warning to the residents of Philadelphia who will be overtaken by a marching line of Godzillas. After exploring several options, the group eventually settles on onions and fractional cascading, only to discover that they themselves are in the line of fire! In the applet, we show step by step details of preprocessing to build the onions with fractional cascading and the subsequent query of the "Godzilla line" against the onion layers. Our video skit and applet can be found at https://ctralie.github.io/GodzillaOnions/
Cite as
Richard Berger, Vincent Ha, David Kratz, Michael Lin, Jeremy Moyer, and Christopher J. Tralie. Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 62:1-62:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{berger_et_al:LIPIcs.SoCG.2023.62,
author = {Berger, Richard and Ha, Vincent and Kratz, David and Lin, Michael and Moyer, Jeremy and Tralie, Christopher J.},
title = {{Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {62:1--62:3},
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.62},
URN = {urn:nbn:de:0030-drops-179129},
doi = {10.4230/LIPIcs.SoCG.2023.62},
annote = {Keywords: convex hulls, onions, fractional cascading, visualization, d3}
}
Document
Media Exposition
Interactive 2D Periodic Graphs (Media Exposition)
Abstract
We present an educational web app for interactively drawing and editing 2D periodic graphs. The user defines the unit cell and the finite set of vertex and edge representatives, from which a sufficiently large fragment of the periodic graph is created for the visualization. The periodic graph can also be modified by applying several transformations, including isometries and relaxations of the unit cell. A finite representation of the infinite periodic graph can be saved in an external file as a quotient graph with Z²-marked edges. Its geometry is recorded using fractional (crystallographic) coordinates. The facial structure of non-crossing periodic graphs can be revealed by the user interactively selecting face representatives. An accompanying video demonstrates the functionality of the web application.
Cite as
Alexandra Camero and Ileana Streinu. Interactive 2D Periodic Graphs (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 63:1-63:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{camero_et_al:LIPIcs.SoCG.2023.63,
author = {Camero, Alexandra and Streinu, Ileana},
title = {{Interactive 2D Periodic Graphs}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {63:1--63:4},
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.63},
URN = {urn:nbn:de:0030-drops-179131},
doi = {10.4230/LIPIcs.SoCG.2023.63},
annote = {Keywords: Periodic graphs, isometric transformations}
}
Document
Media Exposition
Greedy Permutations and Finite Voronoi Diagrams (Media Exposition)
Abstract
We illustrate the computation of a greedy permutation using finite Voronoi diagrams. We describe the neighbor graph, which is a sparse graph data structure that facilitates efficient point location to insert a new Voronoi cell. This data structure is not dependent on a Euclidean metric space. The greedy permutation is computed in O(nlog Δ) time for low-dimensional data using this method [Sariel Har-Peled and Manor Mendel, 2006; Donald R. Sheehy, 2020].
Cite as
Oliver A. Chubet, Paul Macnichol, Parth Parikh, Donald R. Sheehy, and Siddharth S. Sheth. Greedy Permutations and Finite Voronoi Diagrams (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 64:1-64:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{chubet_et_al:LIPIcs.SoCG.2023.64,
author = {Chubet, Oliver A. and Macnichol, Paul and Parikh, Parth and Sheehy, Donald R. and Sheth, Siddharth S.},
title = {{Greedy Permutations and Finite Voronoi Diagrams}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {64:1--64:5},
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.64},
URN = {urn:nbn:de:0030-drops-179146},
doi = {10.4230/LIPIcs.SoCG.2023.64},
annote = {Keywords: greedy permutation, Voronoi diagrams}
}
Document
Media Exposition
The Sum of Squares in Polycubes (Media Exposition)
Abstract
We give several ways to derive and express classic summation problems in terms of polycubes. We visualize them with 3D printed models. The video is here: http://go.ncsu.edu/sum_of_squares.
Cite as
Donald R. Sheehy. The Sum of Squares in Polycubes (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 65:1-65:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{sheehy:LIPIcs.SoCG.2023.65,
author = {Sheehy, Donald R.},
title = {{The Sum of Squares in Polycubes}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {65:1--65:6},
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.65},
URN = {urn:nbn:de:0030-drops-179152},
doi = {10.4230/LIPIcs.SoCG.2023.65},
annote = {Keywords: Archimedes, polycubes, sum of squares}
}
Document
CG Challenge
Constructing Concise Convex Covers via Clique Covers (CG Challenge)
Abstract
This work describes the winning implementation of the CG:SHOP 2023 Challenge. The topic of the Challenge was the convex cover problem: given a polygon P (with holes), find a minimum-cardinality set of convex polygons whose union equals P. We use a three-step approach: (1) Create a suitable partition of P. (2) Compute a visibility graph of the pieces of the partition. (3) Solve a vertex clique cover problem on the visibility graph, from which we then derive the convex cover. This way we capture the geometric difficulty in the first step and the combinatorial difficulty in the third step.
Cite as
Mikkel Abrahamsen, William Bille Meyling, and André Nusser. Constructing Concise Convex Covers via Clique Covers (CG Challenge). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.66,
author = {Abrahamsen, Mikkel and Bille Meyling, William and Nusser, Andr\'{e}},
title = {{Constructing Concise Convex Covers via Clique Covers}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {66:1--66:9},
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.66},
URN = {urn:nbn:de:0030-drops-179164},
doi = {10.4230/LIPIcs.SoCG.2023.66},
annote = {Keywords: Convex cover, Polygons with holes, Algorithm engineering, Vertex clique cover}
}
Document
CG Challenge
Shadoks Approach to Convex Covering (CG Challenge)
Abstract
We describe the heuristics used by the Shadoks team in the CG:SHOP 2023 Challenge. The Challenge consists of 206 instances, each being a polygon with holes. The goal is to cover each instance polygon with a small number of convex polygons. Our general strategy is the following. We find a big collection of large (often maximal) convex polygons inside the instance polygon and then solve several set cover problems to find a small subset of the collection that covers the whole polygon.
Cite as
Guilherme D. da Fonseca. Shadoks Approach to Convex Covering (CG Challenge). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 67:1-67:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{dafonseca:LIPIcs.SoCG.2023.67,
author = {da Fonseca, Guilherme D.},
title = {{Shadoks Approach to Convex Covering}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {67:1--67:9},
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.67},
URN = {urn:nbn:de:0030-drops-179178},
doi = {10.4230/LIPIcs.SoCG.2023.67},
annote = {Keywords: Set cover, covering, polygons, convexity, heuristics, enumeration, simulated annealing, integer programming, computational geometry}
}