Volume
LIPIcs, Volume 189
37th International Symposium on Computational Geometry (SoCG 2021)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG)
Publication Details
- published at: 2021-06-02
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-184-9
- DBLP: db/conf/compgeom/compgeom2021
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 189, SoCG 2021, Complete Volume
Abstract
LIPIcs, Volume 189, SoCG 2021, Complete Volume
Cite as
37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 1-978, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@Proceedings{buchin_et_al:LIPIcs.SoCG.2021,
title = {{LIPIcs, Volume 189, SoCG 2021, Complete Volume}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {1--978},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021},
URN = {urn:nbn:de:0030-drops-137987},
doi = {10.4230/LIPIcs.SoCG.2021},
annote = {Keywords: LIPIcs, Volume 189, SoCG 2021, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{buchin_et_al:LIPIcs.SoCG.2021.0,
author = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {0:i--0:xviii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.0},
URN = {urn:nbn:de:0030-drops-137993},
doi = {10.4230/LIPIcs.SoCG.2021.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
On Laplacians (Invited Talk)
Abstract
This talk outlines recent creations and implementations of Laplacians for distributed systems.
Cite as
Robert Ghrist. On Laplacians (Invited Talk). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{ghrist:LIPIcs.SoCG.2021.1,
author = {Ghrist, Robert},
title = {{On Laplacians}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.1},
URN = {urn:nbn:de:0030-drops-138003},
doi = {10.4230/LIPIcs.SoCG.2021.1},
annote = {Keywords: Laplacian, sheaf theory, applied topology}
}
Document
Invited Talk
3SUM and Related Problems in Fine-Grained Complexity (Invited Talk)
Abstract
3SUM is a simple to state problem: given a set S of n numbers, determine whether S contains three a,b,c so that a+b+c = 0. The fastest algorithms for the problem run in n² poly(log log n)/(log n)² time both when the input numbers are integers [Ilya Baran et al., 2005] (in the word RAM model with O(log n) bit words) and when they are real numbers [Timothy M. Chan, 2020] (in the real RAM model).
A hypothesis that is now central in Fine-Grained Complexity (FGC) states that 3SUM requires n^{2-o(1)} time (on the real RAM for real inputs and on the word RAM with O(log n) bit numbers for integer inputs). This hypothesis was first used in Computational Geometry by Gajentaan and Overmars [A. Gajentaan and M. Overmars, 1995] who built a web of reductions showing that many geometric problems are hard, assuming that 3SUM is hard. The web of reductions within computational geometry has grown considerably since then (see some citations in [V. Vassilevska Williams, 2018]).
A seminal paper by Pǎtraşcu [Mihai Pǎtraşcu, 2010] showed that the integer version of the 3SUM hypothesis can be used to prove polynomial conditional lower bounds for several problems in data structures and graph algorithms as well, extending the implications of the hypothesis to outside computational geometry. Pǎtraşcu proved an important tight equivalence between (integer) 3SUM and a problem called 3SUM-Convolution (see also [Timothy M. Chan and Qizheng He, 2020]) that is easier to use in reductions: given an integer array a of length n, do there exist i,j ∈ [n] so that a[i]+a[j] = a[i+j]. From 3SUM-Convolution, many 3SUM-based hardness results have been proven: e.g. to listing graphs in triangles, dynamically maintaining shortest paths or bipartite matching, subset intersection and many more.
It is interesting to consider more runtime-equivalent formulations of 3SUM, with the goal of uncovering more relationships to different problems. The talk will outline some such equivalences. For instance, 3SUM (over the reals or the integers) is equivalent to All-Numbers-3SUM: given a set S of n numbers, determine for every a ∈ S whether there are b,c ∈ S with a+b+c = 0 (e.g. [V. Vassilevska Williams and R. Williams, 2018]).
The equivalences between 3SUM, 3SUM-Convolution and All-Numbers 3SUM are (n²,n²)-fine-grained equivalences that imply that if there is an O(n^{2-ε}) time algorithm for one of the problems for ε > 0, then there is also an O(n^{2-ε'}) time algorithm for the other problems for some ε' > 0. More generally, for functions a(n),b(n), there is an (a,b)-fine-grained reduction [V. Vassilevska Williams, 2018; V. Vassilevska Williams and R. Williams, 2010; V. Vassilevska Williams and R. Williams, 2018] from problem A to problem B if for every ε > 0 there is a δ > 0 and an O(a(n)^{1-δ}) time algorithm for A that does oracle calls to instances of B of sizes n₁,…,n_k (for some k) so that ∑_{j = 1}^k b(n_j)^{1-ε} ≤ a(n)^{1-δ}. With such a reduction, an O(b(n)^{1-ε}) time algorithm for B can be converted into an O(a(n)^{1-δ}) time algorithm for A by replacing the oracle calls by calls to the B algorithm. A and B are (a,b)-fine-grained equivalent if A (a,b)-reduces to B and B (b,a)-reduces to A.
One of the main open problems in FGC is to determine the relationship between 3SUM and the other central FGC problems, in particular All-Pairs Shortest Paths (APSP). A classical graph problem, APSP in n node graphs has been known to be solvable in O(n³) time since the 1950s. Its fastest known algorithm runs in n³/exp(√{log n}) time [Ryan Williams, 2014]. The APSP Hypothesis states that n^{3-o(1)} time is needed to solve APSP in graphs with integer edge weights in the word-RAM model with O(log n) bit words. It is unknown whether APSP and 3SUM are fine-grained reducible to each other, in either direction. The two problems are very similar. Problems such as (min,+)-convolution (believed to require n^{2-o(1)} time) have tight fine-grained reductions to both APSP and 3SUM, and both 3SUM and APSP have tight fine-grained reductions to problems such as Exact Triangle [V. Vassilevska Williams and R. Williams, 2018; V. Vassilevska and R. Williams, 2009; V. Vassilevska Williams and Ryan Williams, 2013] and (since very recently) Listing triangles in sparse graphs [Mihai Pǎtraşcu, 2010; Tsvi Kopelowitz et al., 2016; V. Vassilevska Williams and Yinzhan Xu, 2020]. The talk will discuss these relationships and some of their implications, e.g. to dynamic algorithms.
Cite as
Virginia Vassilevska Williams. 3SUM and Related Problems in Fine-Grained Complexity (Invited Talk). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{vassilevskawilliams:LIPIcs.SoCG.2021.2,
author = {Vassilevska Williams, Virginia},
title = {{3SUM and Related Problems in Fine-Grained Complexity}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {2:1--2:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.2},
URN = {urn:nbn:de:0030-drops-138014},
doi = {10.4230/LIPIcs.SoCG.2021.2},
annote = {Keywords: fine-grained complexity}
}
Document
Classifying Convex Bodies by Their Contact and Intersection Graphs
Abstract
Let A be a convex body in the plane and A₁,…,A_n be translates of A. Such translates give rise to an intersection graph of A, G = (V,E), with vertices V = {1,… ,n} and edges E = {uv∣ A_u ∩ A_v ≠ ∅}. The subgraph G' = (V, E') satisfying that E' ⊂ E is the set of edges uv for which the interiors of A_u and A_v are disjoint is a unit distance graph of A. If furthermore G' = G, i.e., if the interiors of A_u and A_v are disjoint whenever u≠ v, then G is a contact graph of A.
In this paper, we study which pairs of convex bodies have the same contact, unit distance, or intersection graphs. We say that two convex bodies A and B are equivalent if there exists a linear transformation B' of B such that for any slope, the longest line segments with that slope contained in A and B', respectively, are equally long. For a broad class of convex bodies, including all strictly convex bodies and linear transformations of regular polygons, we show that the contact graphs of A and B are the same if and only if A and B are equivalent. We prove the same statement for unit distance and intersection graphs.
Cite as
Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen, and Peter Michael Reichstein Rasmussen. Classifying Convex Bodies by Their Contact and Intersection Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{aamand_et_al:LIPIcs.SoCG.2021.3,
author = {Aamand, Anders and Abrahamsen, Mikkel and Knudsen, Jakob B{\ae}k Tejs and Rasmussen, Peter Michael Reichstein},
title = {{Classifying Convex Bodies by Their Contact and Intersection Graphs}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {3:1--3:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.3},
URN = {urn:nbn:de:0030-drops-138024},
doi = {10.4230/LIPIcs.SoCG.2021.3},
annote = {Keywords: convex body, contact graph, intersection graph}
}
Document
Approximate Nearest-Neighbor Search for Line Segments
Abstract
Approximate nearest-neighbor search is a fundamental algorithmic problem that continues to inspire study due its essential role in numerous contexts. In contrast to most prior work, which has focused on point sets, we consider nearest-neighbor queries against a set of line segments in ℝ^d, for constant dimension d. Given a set S of n disjoint line segments in ℝ^d and an error parameter ε > 0, the objective is to build a data structure such that for any query point q, it is possible to return a line segment whose Euclidean distance from q is at most (1+ε) times the distance from q to its nearest line segment. We present a data structure for this problem with storage O((n²/ε^d) log (Δ/ε)) and query time O(log (max(n,Δ)/ε)), where Δ is the spread of the set of segments S. Our approach is based on a covering of space by anisotropic elements, which align themselves according to the orientations of nearby segments.
Cite as
Ahmed Abdelkader and David M. Mount. Approximate Nearest-Neighbor Search for Line Segments. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{abdelkader_et_al:LIPIcs.SoCG.2021.4,
author = {Abdelkader, Ahmed and Mount, David M.},
title = {{Approximate Nearest-Neighbor Search for Line Segments}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {4:1--4:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.4},
URN = {urn:nbn:de:0030-drops-138039},
doi = {10.4230/LIPIcs.SoCG.2021.4},
annote = {Keywords: Approximate nearest-neighbor searching, Approximate Voronoi diagrams, Line segments, Macbeath regions}
}
Document
Chasing Puppies: Mobile Beacon Routing on Closed Curves
Abstract
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others’ work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.
Cite as
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.5,
author = {Abrahamsen, Mikkel and Erickson, Jeff and Kostitsyna, Irina and L\"{o}ffler, Maarten and Miltzow, Tillmann and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi and Viglietta, Giovanni},
title = {{Chasing Puppies: Mobile Beacon Routing on Closed Curves}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {5:1--5:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.5},
URN = {urn:nbn:de:0030-drops-138046},
doi = {10.4230/LIPIcs.SoCG.2021.5},
annote = {Keywords: Beacon routing, navigation, generic smooth curves, puppies}
}
Document
Online Packing to Minimize Area or Perimeter
Abstract
We consider online packing problems where we get a stream of axis-parallel rectangles. The rectangles have to be placed in the plane without overlapping, and each rectangle must be placed without knowing the subsequent rectangles. The goal is to minimize the perimeter or the area of the axis-parallel bounding box of the rectangles. We either allow rotations by 90^∘ or translations only.
For the perimeter version we give algorithms with an absolute competitive ratio slightly less than 4 when only translations are allowed and when rotations are also allowed.
We then turn our attention to minimizing the area and show that the competitive ratio of any algorithm is at least Ω(√n), where n is the number of rectangles in the stream, and this holds with and without rotations. We then present algorithms that match this bound in both cases and the competitive ratio is thus optimal to within a constant factor. We also show that the competitive ratio cannot be bounded as a function of Opt. We then consider two special cases.
The first is when all the given rectangles have aspect ratios bounded by some constant. The particular variant where all the rectangles are squares and we want to minimize the area of the bounding square has been studied before and an algorithm with a competitive ratio of 8 has been given [Fekete and Hoffmann, Algorithmica, 2017]. We improve the analysis of the algorithm and show that the ratio is at most 6, which is tight.
The second special case is when all edges have length at least 1. Here, the Ω(√n) lower bound still holds, and we turn our attention to lower bounds depending on Opt. We show that any algorithm for the translational case has a competitive ratio of at least Ω(√{Opt}). If rotations are allowed, we show a lower bound of Ω(∜{Opt}). For both versions, we give algorithms that match the respective lower bounds: With translations only, this is just the algorithm from the general case with competitive ratio O(√n) = O(√{Opt}). If rotations are allowed, we give an algorithm with competitive ratio O(min{√n,∜{Opt}}), thus matching both lower bounds simultaneously.
Cite as
Mikkel Abrahamsen and Lorenzo Beretta. Online Packing to Minimize Area or Perimeter. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.6,
author = {Abrahamsen, Mikkel and Beretta, Lorenzo},
title = {{Online Packing to Minimize Area or Perimeter}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {6:1--6:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.6},
URN = {urn:nbn:de:0030-drops-138054},
doi = {10.4230/LIPIcs.SoCG.2021.6},
annote = {Keywords: Packing, online algorithms}
}
Document
Complexity of Maximum Cut on Interval Graphs
Abstract
We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.
Cite as
Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee, and Bodhayan Roy. Complexity of Maximum Cut on Interval Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{adhikary_et_al:LIPIcs.SoCG.2021.7,
author = {Adhikary, Ranendu and Bose, Kaustav and Mukherjee, Satwik and Roy, Bodhayan},
title = {{Complexity of Maximum Cut on Interval Graphs}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {7:1--7:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.7},
URN = {urn:nbn:de:0030-drops-138067},
doi = {10.4230/LIPIcs.SoCG.2021.7},
annote = {Keywords: Maximum cut, Interval graph, NP-complete}
}
Document
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
Abstract
In the semialgebraic range searching problem, we are given a set of n points in ℝ^d and we want to preprocess the points such that for any query range belonging to a family of constant complexity semialgebraic sets (Tarski cells), all the points intersecting the range can be reported or counted efficiently. When the ranges are composed of simplices, then the problem is well-understood: it can be solved using S(n) space and with Q(n) query time with S(n)Q^d(n) = Õ(n^d) where the Õ(⋅) notation hides polylogarithmic factors and this trade-off is tight (up to n^o(1) factors). Consequently, there exists "low space" structures that use O(n) space with O(n^{1-1/d}) query time and "fast query" structures that use O(n^d) space with O(log^{d+1} n) query time. However, for the general semialgebraic ranges, only "low space" solutions are known, but the best solutions match the same trade-off curve as the simplex queries, with O(n) space and Õ(n^{1-1/d}) query time. It has been conjectured that the same could be done for the "fast query" case but this open problem has stayed unresolved.
Here, we disprove this conjecture. We give the first nontrivial lower bounds for semilagebraic range searching and other related problems. More precisely, we show that any data structure for reporting the points between two concentric circles, a problem that we call 2D annulus reporting problem, with Q(n) query time must use S(n) = Ω^o(n³/Q(n)⁵) space where the Ω^o(⋅) notation hides n^o(1) factors, meaning, for Q(n) = O(log^{O(1)}n), Ω^o(n³) space must be used. In addition, we study the problem of reporting the subset of input points between two polynomials of the form Y = ∑_{i=0}^Δ a_i Xⁱ where values a_0,⋯,a_Δ are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of Ω^o(n^{Δ+1}/Q(n)^{Δ²+Δ}), which shows for Q(n) = O(log^{O(1)}n), we must use Ω^o(n^{Δ+1}) space. We also consider the dual problems of semialgebraic range searching, semialgebraic stabbing problems, and present lower bounds for them. In particular, we show that in linear space, any data structure that solves 2D annulus stabbing problems must use Ω(n^{2/3}) query time. Note that this almost matches the upper bound obtained by lifting 2D annuli to 3D. Like semialgebraic range searching, we also present lower bounds for general semialgebraic slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case.
Cite as
Peyman Afshani and Pingan Cheng. Lower Bounds for Semialgebraic Range Searching and Stabbing Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{afshani_et_al:LIPIcs.SoCG.2021.8,
author = {Afshani, Peyman and Cheng, Pingan},
title = {{Lower Bounds for Semialgebraic Range Searching and Stabbing Problems}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {8:1--8:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.8},
URN = {urn:nbn:de:0030-drops-138072},
doi = {10.4230/LIPIcs.SoCG.2021.8},
annote = {Keywords: Computational Geometry, Data Structures and Algorithms}
}
Document
Rectilinear Steiner Trees in Narrow Strips
Abstract
A rectilinear Steiner tree for a set P of points in ℝ² is a tree that connects the points in P using horizontal and vertical line segments. The goal of {Minimum Rectilinear Steiner Tree} is to find a rectilinear Steiner tree with minimal total length. We investigate how the complexity of {Minimum Rectilinear Steiner Tree} for point sets P inside the strip (-∞,+∞)× [0,δ] depends on the strip width δ. We obtain two main results.
- We present an algorithm with running time n^O(√δ) for sparse point sets, that is, point sets where each 1×δ rectangle inside the strip contains O(1) points.
- For random point sets, where the points are chosen randomly inside a rectangle of height δ and expected width n, we present an algorithm that is fixed-parameter tractable with respect to δ and linear in n. It has an expected running time of 2^{O(δ √{δ})} n.
Cite as
Henk Alkema and Mark de Berg. Rectilinear Steiner Trees in Narrow Strips. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{alkema_et_al:LIPIcs.SoCG.2021.9,
author = {Alkema, Henk and de Berg, Mark},
title = {{Rectilinear Steiner Trees in Narrow Strips}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {9:1--9:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.9},
URN = {urn:nbn:de:0030-drops-138081},
doi = {10.4230/LIPIcs.SoCG.2021.9},
annote = {Keywords: Computational geometry, fixed-parameter tractable algorithms}
}
Document
Characterizing Universal Reconfigurability of Modular Pivoting Robots
Abstract
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using O(n³) monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN'18] that we consider of independent interest.
Cite as
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán. Characterizing Universal Reconfigurability of Modular Pivoting Robots. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{a.akitaya_et_al:LIPIcs.SoCG.2021.10,
author = {A. Akitaya, Hugo and Demaine, Erik D. and Gonczi, Andrei and Hendrickson, Dylan H. and Hesterberg, Adam and Korman, Matias and Korten, Oliver and Lynch, Jayson and Parada, Irene and Sacrist\'{a}n, Vera},
title = {{Characterizing Universal Reconfigurability of Modular Pivoting Robots}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {10:1--10:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.10},
URN = {urn:nbn:de:0030-drops-138094},
doi = {10.4230/LIPIcs.SoCG.2021.10},
annote = {Keywords: reconfiguration, geometric algorithm, PSPACE-hardness, pivoting hexagons, pivoting squares, modular robots}
}
Document
Adjacency Graphs of Polyhedral Surfaces
Abstract
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in ℝ³. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains K_5, K_{5,81}, or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, K_{4,4}, and K_{3,5} can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube.
Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in Ω(n log n). From the non-realizability of K_{5,81}, we obtain that any realizable n-vertex graph has 𝒪(n^{9/5}) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.
Cite as
Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{arseneva_et_al:LIPIcs.SoCG.2021.11,
author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander},
title = {{Adjacency Graphs of Polyhedral Surfaces}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {11:1--11:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.11},
URN = {urn:nbn:de:0030-drops-138107},
doi = {10.4230/LIPIcs.SoCG.2021.11},
annote = {Keywords: polyhedral complexes, realizability, contact representation}
}
Document
On Undecided LP, Clustering and Active Learning
Abstract
We study colored coverage and clustering problems. Here, we are given a colored point set, where the points are covered by k (unknown) clusters, which are monochromatic (i.e., all the points covered by the same cluster have the same color). The access to the colors of the points (or even the points themselves) is provided indirectly via various oracle queries (such as nearest neighbor, or separation queries). We show that one can correctly deduce the color of all the points (i.e., compute a monochromatic clustering of the points) using a polylogarithmic number of queries, if the number of clusters is a constant.
We investigate several variants of this problem, including Undecided Linear Programming and covering of points by k monochromatic balls.
Cite as
Stav Ashur and Sariel Har-Peled. On Undecided LP, Clustering and Active Learning. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{ashur_et_al:LIPIcs.SoCG.2021.12,
author = {Ashur, Stav and Har-Peled, Sariel},
title = {{On Undecided LP, Clustering and Active Learning}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {12:1--12:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.12},
URN = {urn:nbn:de:0030-drops-138116},
doi = {10.4230/LIPIcs.SoCG.2021.12},
annote = {Keywords: Linear Programming, Active learning, Classification}
}
Document
Two-Sided Kirszbraun Theorem
Abstract
In this paper, we prove a two-sided variant of the Kirszbraun theorem. Consider an arbitrary subset X of Euclidean space and its superset Y. Let f be a 1-Lipschitz map from X to ℝ^m. The Kirszbraun theorem states that the map f can be extended to a 1-Lipschitz map ̃ f from Y to ℝ^m. While the extension ̃ f does not increase distances between points, there is no guarantee that it does not decrease distances significantly. In fact, ̃ f may even map distinct points to the same point (that is, it can infinitely decrease some distances). However, we prove that there exists a (1 + ε)-Lipschitz outer extension f̃:Y → ℝ^{m'} that does not decrease distances more than "necessary". Namely, ‖f̃(x) - f̃(y)‖ ≥ c √{ε} min(‖x-y‖, inf_{a,b ∈ X} (‖x - a‖ + ‖f(a) - f(b)‖ + ‖b-y‖)) for some absolutely constant c > 0. This bound is asymptotically optimal, since no L-Lipschitz extension g can have ‖g(x) - g(y)‖ > L min(‖x-y‖, inf_{a,b ∈ X} (‖x - a‖ + ‖f(a) - f(b)‖ + ‖b-y‖)) even for a single pair of points x and y.
In some applications, one is interested in the distances ‖f̃(x) - f̃(y)‖ between images of points x,y ∈ Y rather than in the map f̃ itself. The standard Kirszbraun theorem does not provide any method of computing these distances without computing the entire map ̃ f first. In contrast, our theorem provides a simple approximate formula for distances ‖f̃(x) - f̃(y)‖.
Cite as
Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, and Yury Makarychev. Two-Sided Kirszbraun Theorem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{backurs_et_al:LIPIcs.SoCG.2021.13,
author = {Backurs, Arturs and Mahabadi, Sepideh and Makarychev, Konstantin and Makarychev, Yury},
title = {{Two-Sided Kirszbraun Theorem}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {13:1--13:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.13},
URN = {urn:nbn:de:0030-drops-138129},
doi = {10.4230/LIPIcs.SoCG.2021.13},
annote = {Keywords: Kirszbraun theorem, Lipschitz map, Outer-extension, Two-sided extension}
}
Document
Orientation Preserving Maps of the Square Grid
Abstract
For a finite set A ⊂ ℝ², a map φ: A → ℝ² is orientation preserving if for every non-collinear triple u,v,w ∈ A the orientation of the triangle u,v,w is the same as that of the triangle φ(u),φ(v),φ(w). We prove that for every n ∈ ℕ and for every ε > 0 there is N = N(n,ε) ∈ ℕ such that the following holds. Assume that φ:G(N) → ℝ² is an orientation preserving map where G(N) is the grid {(i,j) ∈ ℤ²: -N ≤ i,j ≤ N}. Then there is an affine transformation ψ :ℝ² → ℝ² and a ∈ ℤ² such that a+G(n) ⊂ G(N) and ‖ψ∘φ (z)-z‖ < ε for every z ∈ a+G(n). This result was previously proved in a completely different way by Nešetřil and Valtr, without obtaining any bound on N. Our proof gives N(n,ε) = O(n⁴ε^{-2}).
Cite as
Imre Bárány, Attila Pór, and Pavel Valtr. Orientation Preserving Maps of the Square Grid. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{barany_et_al:LIPIcs.SoCG.2021.14,
author = {B\'{a}r\'{a}ny, Imre and P\'{o}r, Attila and Valtr, Pavel},
title = {{Orientation Preserving Maps of the Square Grid}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {14:1--14:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.14},
URN = {urn:nbn:de:0030-drops-138130},
doi = {10.4230/LIPIcs.SoCG.2021.14},
annote = {Keywords: square grid, plane, order type}
}
Document
Light Euclidean Steiner Spanners in the Plane
Abstract
Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in ℝ^d. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on ε > 0 and d ∈ ℕ of the minimum lightness of a (1+ε)-spanner, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ≥ Ω(√n) is the spread of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness Õ(ε^{-(d+1)/2}) in dimensions d ≥ 3. Recently, Bhore and Tóth (2020) established a lower bound of Ω(ε^{-d/2}) for the lightness of Steiner (1+ε)-spanners in ℝ^d, for d ≥ 2. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions d ≥ 2.
In this work, we show that for every finite set of points in the plane and every ε > 0, there exists a Euclidean Steiner (1+ε)-spanner of lightness O(ε^{-1}); this matches the lower bound for d = 2. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.
Cite as
Sujoy Bhore and Csaba D. Tóth. Light Euclidean Steiner Spanners in the Plane. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{bhore_et_al:LIPIcs.SoCG.2021.15,
author = {Bhore, Sujoy and T\'{o}th, Csaba D.},
title = {{Light Euclidean Steiner Spanners in the Plane}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {15:1--15:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.15},
URN = {urn:nbn:de:0030-drops-138145},
doi = {10.4230/LIPIcs.SoCG.2021.15},
annote = {Keywords: Geometric spanner, lightness, minimum weight}
}
Document
Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory
Abstract
Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation.
Cite as
Ranita Biswas, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{biswas_et_al:LIPIcs.SoCG.2021.16,
author = {Biswas, Ranita and Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza},
title = {{Counting Cells of Order-k Voronoi Tessellations in \mathbb{R}³ with Morse Theory}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {16:1--16:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.16},
URN = {urn:nbn:de:0030-drops-138152},
doi = {10.4230/LIPIcs.SoCG.2021.16},
annote = {Keywords: Voronoi tessellations, Delaunay mosaics, arrangements, convex polytopes, Morse theory, counting}
}
Document
Tracing Isomanifolds in ℝ^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations
Abstract
Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art.
Cite as
Jean-Daniel Boissonnat, Siargey Kachanovich, and Mathijs Wintraecken. Tracing Isomanifolds in ℝ^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2021.17,
author = {Boissonnat, Jean-Daniel and Kachanovich, Siargey and Wintraecken, Mathijs},
title = {{Tracing Isomanifolds in \mathbb{R}^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {17:1--17:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.17},
URN = {urn:nbn:de:0030-drops-138163},
doi = {10.4230/LIPIcs.SoCG.2021.17},
annote = {Keywords: Coxeter triangulation, Kuhn triangulation, permutahedron, PL-approximations, isomanifolds/solution manifolds/isosurfacing}
}
Document
Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation
Abstract
Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible.
Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size n and m, the Hausdorff distance under translation can be computed in time 𝒪̃(nm) for the L₁ and L_∞ norm [Chew, Kedem SWAT'92] and 𝒪̃(nm (n+m)) for the L₂ norm [Huttenlocher, Kedem, Sharir DCG'93].
As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of (nm)^{1-o(1)} for L₁ and L_∞ assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of n^{2-o(1)} for L₂ in the imbalanced case of m = 𝒪(1) assuming the 3SUM Hypothesis.
Cite as
Karl Bringmann and André Nusser. Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{bringmann_et_al:LIPIcs.SoCG.2021.18,
author = {Bringmann, Karl and Nusser, Andr\'{e}},
title = {{Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {18:1--18:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.18},
URN = {urn:nbn:de:0030-drops-138177},
doi = {10.4230/LIPIcs.SoCG.2021.18},
annote = {Keywords: Hausdorff Distance Under Translation, Fine-Grained Complexity Theory, Lower Bounds}
}
Document
Optimal Bounds for the Colorful Fractional Helly Theorem
Abstract
The well known fractional Helly theorem and colorful Helly theorem can be merged into the so called colorful fractional Helly theorem. It states: for every α ∈ (0, 1] and every non-negative integer d, there is β_{col} = β_{col}(α, d) ∈ (0, 1] with the following property. Let ℱ₁, … , ℱ_{d+1} be finite nonempty families of convex sets in ℝ^d of sizes n₁, … , n_{d+1}, respectively. If at least α n₁ n₂ ⋯ n_{d+1} of the colorful (d+1)-tuples have a nonempty intersection, then there is i ∈ [d+1] such that ℱ_i contains a subfamily of size at least β_{col} n_i with a nonempty intersection. (A colorful (d+1)-tuple is a (d+1)-tuple (F₁, … , F_{d+1}) such that F_i belongs to ℱ_i for every i.)
The colorful fractional Helly theorem was first stated and proved by Bárány, Fodor, Montejano, Oliveros, and Pór in 2014 with β_{col} = α/(d+1). In 2017 Kim proved the theorem with better function β_{col}, which in particular tends to 1 when α tends to 1. Kim also conjectured what is the optimal bound for β_{col}(α, d) and provided the upper bound example for the optimal bound. The conjectured bound coincides with the optimal bounds for the (non-colorful) fractional Helly theorem proved independently by Eckhoff and Kalai around 1984.
We verify Kim’s conjecture by extending Kalai’s approach to the colorful scenario. Moreover, we obtain optimal bounds also in a more general setting when we allow several sets of the same color.
Cite as
Denys Bulavka, Afshin Goodarzi, and Martin Tancer. Optimal Bounds for the Colorful Fractional Helly Theorem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{bulavka_et_al:LIPIcs.SoCG.2021.19,
author = {Bulavka, Denys and Goodarzi, Afshin and Tancer, Martin},
title = {{Optimal Bounds for the Colorful Fractional Helly Theorem}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {19:1--19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.19},
URN = {urn:nbn:de:0030-drops-138186},
doi = {10.4230/LIPIcs.SoCG.2021.19},
annote = {Keywords: colorful fractional Helly theorem, d-collapsible, exterior algebra, d-representable}
}
Document
An Integer Programming Formulation Using Convex Polygons for the Convex Partition Problem
Abstract
A convex partition of a point set P in the plane is a planar partition of the convex hull of P into empty convex polygons or internal faces whose extreme points belong to P. In a convex partition, the union of the internal faces give the convex hull of P and the interiors of the polygons are pairwise disjoint. Moreover, no polygon is allowed to contain a point of P in its interior. The problem is to find a convex partition with the minimum number of internal faces. The problem has been shown to be NP-hard and was recently used in the CG:SHOP Challenge 2020. We propose a new integer linear programming (IP) formulation that considerably improves over the existing one. It relies on the representation of faces as opposed to segments and points. A number of geometric properties are used to strengthen it. Data sets of 100 points are easily solved to optimality and the lower bounds provided by the model can be computed up to 300 points.
Cite as
Hadrien Cambazard and Nicolas Catusse. An Integer Programming Formulation Using Convex Polygons for the Convex Partition Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{cambazard_et_al:LIPIcs.SoCG.2021.20,
author = {Cambazard, Hadrien and Catusse, Nicolas},
title = {{An Integer Programming Formulation Using Convex Polygons for the Convex Partition Problem}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {20:1--20:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.20},
URN = {urn:nbn:de:0030-drops-138198},
doi = {10.4230/LIPIcs.SoCG.2021.20},
annote = {Keywords: convex partition, integer programming, geometric optimization}
}
Document
Geometric Algorithms for Sampling the Flux Space of Metabolic Networks
Abstract
Systems Biology is a fundamental field and paradigm that introduces a new era in Biology. The crux of its functionality and usefulness relies on metabolic networks that model the reactions occurring inside an organism and provide the means to understand the underlying mechanisms that govern biological systems. Even more, metabolic networks have a broader impact that ranges from resolution of ecosystems to personalized medicine.
The analysis of metabolic networks is a computational geometry oriented field as one of the main operations they depend on is sampling uniformly points from polytopes; the latter provides a representation of the steady states of the metabolic networks. However, the polytopes that result from biological data are of very high dimension (to the order of thousands) and in most, if not all, the cases are considerably skinny. Therefore, to perform uniform random sampling efficiently in this setting, we need a novel algorithmic and computational framework specially tailored for the properties of metabolic networks.
We present a complete software framework to handle sampling in metabolic networks. Its backbone is a Multiphase Monte Carlo Sampling (MMCS) algorithm that unifies rounding and sampling in one pass, obtaining both upon termination. It exploits an improved variant of the Billiard Walk that enjoys faster arithmetic complexity per step. We demonstrate the efficiency of our approach by performing extensive experiments on various metabolic networks. Notably, sampling on the most complicated human metabolic network accessible today, Recon3D, corresponding to a polytope of dimension 5335, took less than 30 hours. To our knowledge, that is out of reach for existing software.
Cite as
Apostolos Chalkis, Vissarion Fisikopoulos, Elias Tsigaridas, and Haris Zafeiropoulos. Geometric Algorithms for Sampling the Flux Space of Metabolic Networks. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{chalkis_et_al:LIPIcs.SoCG.2021.21,
author = {Chalkis, Apostolos and Fisikopoulos, Vissarion and Tsigaridas, Elias and Zafeiropoulos, Haris},
title = {{Geometric Algorithms for Sampling the Flux Space of Metabolic Networks}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {21:1--21:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.21},
URN = {urn:nbn:de:0030-drops-138201},
doi = {10.4230/LIPIcs.SoCG.2021.21},
annote = {Keywords: Flux analysis, metabolic networks, convex polytopes, random walks, sampling}
}
Document
A Family of Metrics from the Truncated Smoothing of Reeb Graphs
Abstract
In this paper, we introduce an extension of smoothing on Reeb graphs, which we call truncated smoothing; this in turn allows us to define a new family of metrics which generalize the interleaving distance for Reeb graphs. Intuitively, we "chop off" parts near local minima and maxima during the course of smoothing, where the amount cut is controlled by a parameter τ. After formalizing truncation as a functor, we show that when applied after the smoothing functor, this prevents extensive expansion of the range of the function, and yields particularly nice properties (such as maintaining connectivity) when combined with smoothing for 0 ≤ τ ≤ 2ε, where ε is the smoothing parameter. Then, for the restriction of τ ∈ [0,ε], we have additional structure which we can take advantage of to construct a categorical flow for any choice of slope m ∈ [0,1]. Using the infrastructure built for a category with a flow, this then gives an interleaving distance for every m ∈ [0,1], which is a generalization of the original interleaving distance, which is the case m = 0. While the resulting metrics are not stable, we show that any pair of these for m, m' ∈ [0,1) are strongly equivalent metrics, which in turn gives stability of each metric up to a multiplicative constant. We conclude by discussing implications of this metric within the broader family of metrics for Reeb graphs.
Cite as
Erin Wolf Chambers, Elizabeth Munch, and Tim Ophelders. A Family of Metrics from the Truncated Smoothing of Reeb Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{chambers_et_al:LIPIcs.SoCG.2021.22,
author = {Chambers, Erin Wolf and Munch, Elizabeth and Ophelders, Tim},
title = {{A Family of Metrics from the Truncated Smoothing of Reeb Graphs}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {22:1--22:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.22},
URN = {urn:nbn:de:0030-drops-138218},
doi = {10.4230/LIPIcs.SoCG.2021.22},
annote = {Keywords: Reeb graphs, interleaving distance, graphical signatures}
}
Document
Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries
Abstract
In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize that the manifold and the curve are both inputs to the problem. Moreover, our algorithm also works if the curve is given as a compressed word. Previously, such an algorithm was known for simple (non-compressed) curves, and, in very limited cases, for curves with self-intersections. Furthermore, our algorithm is fixed-parameter tractable in the complexity of the input 3-manifold.
As part of our proof, we obtain new polynomial-time algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomial-time algorithm which, given an orientable surface and a compressed loop on the surface, computes a canonical form for the loop as a compressed word. In particular, contractibility of compressed curves on surfaces can be decided in polynomial time; prior published work considered only constant genus surfaces. More generally, we solve the following normal subgroup membership problem in polynomial time: given an arbitrary orientable surface, a compressed closed curve γ, and a collection of disjoint normal curves Δ, there is a polynomial-time algorithm to decide if γ lies in the normal subgroup generated by components of Δ in the fundamental group of the surface after attaching the curves to a basepoint.
Cite as
Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay, and Salman Parsa. Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{chambers_et_al:LIPIcs.SoCG.2021.23,
author = {Chambers, Erin Wolf and Lazarus, Francis and de Mesmay, Arnaud and Parsa, Salman},
title = {{Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {23:1--23:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.23},
URN = {urn:nbn:de:0030-drops-138223},
doi = {10.4230/LIPIcs.SoCG.2021.23},
annote = {Keywords: 3-manifolds, surfaces, low-dimensional topology, contractibility, compressed curves}
}
Document
Faster Algorithms for Largest Empty Rectangles and Boxes
Abstract
We revisit a classical problem in computational geometry: finding the largest-volume axis-aligned empty box (inside a given bounding box) amidst n given points in d dimensions. Previously, the best algorithms known have running time O(nlog²n) for d = 2 (by Aggarwal and Suri [SoCG'87]) and near n^d for d ≥ 3. We describe faster algorithms with running time
- O(n2^{O(log^*n)}log n) for d = 2,
- O(n^{2.5+o(1)}) time for d = 3, and
- Õ(n^{(5d+2)/6}) time for any constant d ≥ 4.
To obtain the higher-dimensional result, we adapt and extend previous techniques for Klee’s measure problem to optimize certain objective functions over the complement of a union of orthants.
Cite as
Timothy M. Chan. Faster Algorithms for Largest Empty Rectangles and Boxes. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{chan:LIPIcs.SoCG.2021.24,
author = {Chan, Timothy M.},
title = {{Faster Algorithms for Largest Empty Rectangles and Boxes}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {24:1--24:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.24},
URN = {urn:nbn:de:0030-drops-138231},
doi = {10.4230/LIPIcs.SoCG.2021.24},
annote = {Keywords: Largest empty rectangle, largest empty box, Klee’s measure problem}
}
Document
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time
Abstract
We study geometric set cover problems in dynamic settings, allowing insertions and deletions of points and objects. We present the first dynamic data structure that can maintain an O(1)-approximation in sublinear update time for set cover for axis-aligned squares in 2D . More precisely, we obtain randomized update time O(n^{2/3+δ}) for an arbitrarily small constant δ > 0. Previously, a dynamic geometric set cover data structure with sublinear update time was known only for unit squares by Agarwal, Chang, Suri, Xiao, and Xue [SoCG 2020]. If only an approximate size of the solution is needed, then we can also obtain sublinear amortized update time for disks in 2D and halfspaces in 3D . As a byproduct, our techniques for dynamic set cover also yield an optimal randomized O(nlog n)-time algorithm for static set cover for 2D disks and 3D halfspaces, improving our earlier O(nlog n(log log n)^{O(1)}) result [SoCG 2020].
Cite as
Timothy M. Chan and Qizheng He. More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{chan_et_al:LIPIcs.SoCG.2021.25,
author = {Chan, Timothy M. and He, Qizheng},
title = {{More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {25:1--25:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.25},
URN = {urn:nbn:de:0030-drops-138244},
doi = {10.4230/LIPIcs.SoCG.2021.25},
annote = {Keywords: Geometric set cover, approximation algorithms, dynamic data structures, sublinear algorithms, random sampling}
}
Document
Approximating the (Continuous) Fréchet Distance
Abstract
We describe the first strongly subquadratic time algorithm with subexponential approximation ratio for approximately computing the Fréchet distance between two polygonal chains. Specifically, let P and Q be two polygonal chains with n vertices in d-dimensional Euclidean space, and let α ∈ [√n, n]. Our algorithm deterministically finds an O(α)-approximate Fréchet correspondence in time O((n³ / α²) log n). In particular, we get an O(n)-approximation in near-linear O(n log n) time, a vast improvement over the previously best know result, a linear time 2^O(n)-approximation. As part of our algorithm, we also describe how to turn any approximate decision procedure for the Fréchet distance into an approximate optimization algorithm whose approximation ratio is the same up to arbitrarily small constant factors. The transformation into an approximate optimization algorithm increases the running time of the decision procedure by only an O(log n) factor.
Cite as
Connor Colombe and Kyle Fox. Approximating the (Continuous) Fréchet Distance. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{colombe_et_al:LIPIcs.SoCG.2021.26,
author = {Colombe, Connor and Fox, Kyle},
title = {{Approximating the (Continuous) Fr\'{e}chet Distance}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {26:1--26:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.26},
URN = {urn:nbn:de:0030-drops-138259},
doi = {10.4230/LIPIcs.SoCG.2021.26},
annote = {Keywords: Fr\'{e}chet distance, approximation algorithm, approximate decision procedure}
}
Document
Computing the Multicover Bifiltration
Abstract
Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.
Cite as
René Corbet, Michael Kerber, Michael Lesnick, and Georg Osang. Computing the Multicover Bifiltration. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{corbet_et_al:LIPIcs.SoCG.2021.27,
author = {Corbet, Ren\'{e} and Kerber, Michael and Lesnick, Michael and Osang, Georg},
title = {{Computing the Multicover Bifiltration}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {27:1--27:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.27},
URN = {urn:nbn:de:0030-drops-138260},
doi = {10.4230/LIPIcs.SoCG.2021.27},
annote = {Keywords: Bifiltrations, nerves, higher-order Delaunay complexes, higher-order Voronoi diagrams, rhomboid tiling, multiparameter persistent homology, denoising}
}
Document
Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications
Abstract
Given a set system (X, S), constructing a matching of X with low crossing number is a key tool in combinatorics and algorithms. In this paper we present a new sampling-based algorithm which is applicable to finite set systems. Let n = |X|, m = | S| and assume that X has a perfect matching M such that any set in 𝒮 crosses at most κ = Θ(n^γ) edges of M. In the case γ = 1- 1/d, our algorithm computes a perfect matching of X with expected crossing number at most 10 κ, in expected time Õ (n^{2+(2/d)} + mn^(2/d)).
As an immediate consequence, we get improved bounds for constructing low-crossing matchings for a slew of both abstract and geometric problems, including many basic geometric set systems (e.g., balls in ℝ^d). This further implies improved algorithms for many well-studied problems such as construction of ε-approximations. Our work is related to two earlier themes: the work of Varadarajan (STOC '10) / Chan et al. (SODA '12) that avoids spatial partitionings for constructing ε-nets, and of Chan (DCG '12) that gives an optimal algorithm for matchings with respect to hyperplanes in ℝ^d.
Another major advantage of our method is its simplicity. An implementation of a variant of our algorithm in C++ is available on Github; it is approximately 200 lines of basic code without any non-trivial data-structure. Since the start of the study of matchings with low-crossing numbers with respect to half-spaces in the 1980s, this is the first implementation made possible for dimensions larger than 2.
Cite as
Mónika Csikós and Nabil H. Mustafa. Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{csikos_et_al:LIPIcs.SoCG.2021.28,
author = {Csik\'{o}s, M\'{o}nika and Mustafa, Nabil H.},
title = {{Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {28:1--28:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.28},
URN = {urn:nbn:de:0030-drops-138273},
doi = {10.4230/LIPIcs.SoCG.2021.28},
annote = {Keywords: Matchings, crossing numbers, approximations}
}
Document
Colouring Polygon Visibility Graphs and Their Generalizations
Abstract
Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with clique number ω has chromatic number at most 3⋅4^{ω-1}. The proof is carried through in the setting of ordered graphs; we identify two conditions satisfied by every curve pseudo-visibility graph (considered as an ordered graph) and prove that they are sufficient for the claimed bound. The proof is algorithmic: both the clique number and a colouring with the claimed number of colours can be computed in polynomial time.
Cite as
James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak. Colouring Polygon Visibility Graphs and Their Generalizations. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{davies_et_al:LIPIcs.SoCG.2021.29,
author = {Davies, James and Krawczyk, Tomasz and McCarty, Rose and Walczak, Bartosz},
title = {{Colouring Polygon Visibility Graphs and Their Generalizations}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {29:1--29:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.29},
URN = {urn:nbn:de:0030-drops-138281},
doi = {10.4230/LIPIcs.SoCG.2021.29},
annote = {Keywords: Visibility graphs, \chi-boundedness, pseudoline arrangements, ordered graphs}
}
Document
Computing Zigzag Persistence on Graphs in Near-Linear Time
Abstract
Graphs model real-world circumstances in many applications where they may constantly change to capture the dynamic behavior of the phenomena. Topological persistence which provides a set of birth and death pairs for the topological features is one instrument for analyzing such changing graph data. However, standard persistent homology defined over a growing space cannot always capture such a dynamic process unless shrinking with deletions is also allowed. Hence, zigzag persistence which incorporates both insertions and deletions of simplices is more appropriate in such a setting. Unlike standard persistence which admits nearly linear-time algorithms for graphs, such results for the zigzag version improving the general O(m^ω) time complexity are not known, where ω < 2.37286 is the matrix multiplication exponent. In this paper, we propose algorithms for zigzag persistence on graphs which run in near-linear time. Specifically, given a filtration with m additions and deletions on a graph with n vertices and edges, the algorithm for 0-dimension runs in O(mlog² n+mlog m) time and the algorithm for 1-dimension runs in O(mlog⁴ n) time. The algorithm for 0-dimension draws upon another algorithm designed originally for pairing critical points of Morse functions on 2-manifolds. The algorithm for 1-dimension pairs a negative edge with the earliest positive edge so that a 1-cycle containing both edges resides in all intermediate graphs. Both algorithms achieve the claimed time complexity via dynamic graph data structures proposed by Holm et al. In the end, using Alexander duality, we extend the algorithm for 0-dimension to compute the (p-1)-dimensional zigzag persistence for ℝ^p-embedded complexes in O(mlog² n+mlog m+nlog n) time.
Cite as
Tamal K. Dey and Tao Hou. Computing Zigzag Persistence on Graphs in Near-Linear Time. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{dey_et_al:LIPIcs.SoCG.2021.30,
author = {Dey, Tamal K. and Hou, Tao},
title = {{Computing Zigzag Persistence on Graphs in Near-Linear Time}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {30:1--30:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.30},
URN = {urn:nbn:de:0030-drops-138292},
doi = {10.4230/LIPIcs.SoCG.2021.30},
annote = {Keywords: persistent homology, zigzag persistence, graph filtration, dynamic networks}
}
Document
Minimal Delaunay Triangulations of Hyperbolic Surfaces
Abstract
Motivated by recent work on Delaunay triangulations of hyperbolic surfaces, we consider the minimal number of vertices of such triangulations. First, we show that every hyperbolic surface of genus g has a simplicial Delaunay triangulation with O(g) vertices, where edges are given by distance paths. Then, we construct a class of hyperbolic surfaces for which the order of this bound is optimal. Finally, to give a general lower bound, we show that the Ω(√g) lower bound for the number of vertices of a simplicial triangulation of a topological surface of genus g is tight for hyperbolic surfaces as well.
Cite as
Matthijs Ebbens, Hugo Parlier, and Gert Vegter. Minimal Delaunay Triangulations of Hyperbolic Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{ebbens_et_al:LIPIcs.SoCG.2021.31,
author = {Ebbens, Matthijs and Parlier, Hugo and Vegter, Gert},
title = {{Minimal Delaunay Triangulations of Hyperbolic Surfaces}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {31:1--31:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.31},
URN = {urn:nbn:de:0030-drops-138305},
doi = {10.4230/LIPIcs.SoCG.2021.31},
annote = {Keywords: Delaunay triangulations, hyperbolic surfaces, metric graph embeddings, moduli spaces}
}
Document
The Density Fingerprint of a Periodic Point Set
Abstract
Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functions that facilitates the efficient search for new materials and material properties. We prove invariance under isometries, continuity, and completeness in the generic case, which are necessary features for the reliable comparison of crystals. The proof of continuity integrates methods from discrete geometry and lattice theory, while the proof of generic completeness combines techniques from geometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and related inclusion-exclusion formulae. We have implemented the algorithm and describe its application to crystal structure prediction.
Cite as
Herbert Edelsbrunner, Teresa Heiss, Vitaliy Kurlin, Philip Smith, and Mathijs Wintraecken. The Density Fingerprint of a Periodic Point Set. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2021.32,
author = {Edelsbrunner, Herbert and Heiss, Teresa and Kurlin, Vitaliy and Smith, Philip and Wintraecken, Mathijs},
title = {{The Density Fingerprint of a Periodic Point Set}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {32:1--32:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.32},
URN = {urn:nbn:de:0030-drops-138310},
doi = {10.4230/LIPIcs.SoCG.2021.32},
annote = {Keywords: Lattices, periodic sets, isometries, Dirichlet-Voronoi domains, Brillouin zones, bottleneck distance, stability, continuity, crystal database}
}
Document
On the Edge Crossings of the Greedy Spanner
Abstract
The greedy t-spanner of a set of points in the plane is an undirected graph constructed by considering pairs of points in order by distance, and connecting a pair by an edge when there does not already exist a path connecting that pair with length at most t times the Euclidean distance. We prove that, for any t > 1, these graphs have at most a linear number of crossings, and more strongly that the intersection graph of edges in a greedy t-spanner has bounded degeneracy. As a consequence, we prove a separator theorem for greedy spanners: any k-vertex subgraph of a greedy spanner can be partitioned into sub-subgraphs of size a constant fraction smaller, by the removal of O(√k) vertices. A recursive separator hierarchy for these graphs can be constructed from their planarizations in linear time, or in near-linear time if the planarization is unknown.
Cite as
David Eppstein and Hadi Khodabandeh. On the Edge Crossings of the Greedy Spanner. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{eppstein_et_al:LIPIcs.SoCG.2021.33,
author = {Eppstein, David and Khodabandeh, Hadi},
title = {{On the Edge Crossings of the Greedy Spanner}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {33:1--33:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.33},
URN = {urn:nbn:de:0030-drops-138328},
doi = {10.4230/LIPIcs.SoCG.2021.33},
annote = {Keywords: Geometric Spanners, Greedy Spanners, Separators, Crossing Graph, Sparsity}
}
Document
On Ray Shooting for Triangles in 3-Space and Related Problems
Abstract
We consider several problems that involve lines in three dimensions, and present improved algorithms for solving them. The problems include (i) ray shooting amid triangles in ℝ³, (ii) reporting intersections between query lines (segments, or rays) and input triangles, as well as approximately counting the number of such intersections, (iii) computing the intersection of two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections in a set of lines in ℝ³, and (v) output-sensitive construction of an arrangement of triangles in three dimensions.
Our approach is based on the polynomial partitioning technique.
For example, our ray-shooting algorithm processes a set of n triangles in ℝ³ into a data structure for answering ray shooting queries amid the given triangles, which uses O(n^{3/2+ε}) storage and preprocessing, and answers a query in O(n^{1/2+ε}) time, for any ε > 0. This is a significant improvement over known results, obtained more than 25 years ago, in which, with this amount of storage, the query time bound is roughly n^{5/8}. The algorithms for the other problems have similar performance bounds, with similar improvements over previous results.
We also derive a nontrivial improved tradeoff between storage and query time. Using it, we obtain algorithms that answer m queries on n objects in max{O(m^{2/3}n^{5/6+{ε}} + n^{1+ε}), O(m^{5/6+ε}n^{2/3} + m^{1+ε})} time, for any ε > 0, again an improvement over the earlier bounds.
Cite as
Esther Ezra and Micha Sharir. On Ray Shooting for Triangles in 3-Space and Related Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{ezra_et_al:LIPIcs.SoCG.2021.34,
author = {Ezra, Esther and Sharir, Micha},
title = {{On Ray Shooting for Triangles in 3-Space and Related Problems}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {34:1--34:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.34},
URN = {urn:nbn:de:0030-drops-138332},
doi = {10.4230/LIPIcs.SoCG.2021.34},
annote = {Keywords: Ray shooting, Three dimensions, Polynomial partitioning, Tradeoff}
}
Document
On Rich Lenses in Planar Arrangements of Circles and Related Problems
Abstract
We show that the maximum number of pairwise non-overlapping k-rich lenses (lenses formed by at least k circles) in an arrangement of n circles in the plane is O(n^{3/2}log(n / k^3) k^{-5/2} + n/k), and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is O(n^{3/2}log(n/k^3) k^{-3/2} + n). Two independent proofs of these bounds are given, each interesting in its own right (so we believe). We then show that these bounds lead to the known bound of Agarwal et al. (JACM 2004) and Marcus and Tardos (JCTA 2006) on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.
Cite as
Esther Ezra, Orit E. Raz, Micha Sharir, and Joshua Zahl. On Rich Lenses in Planar Arrangements of Circles and Related Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{ezra_et_al:LIPIcs.SoCG.2021.35,
author = {Ezra, Esther and Raz, Orit E. and Sharir, Micha and Zahl, Joshua},
title = {{On Rich Lenses in Planar Arrangements of Circles and Related Problems}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {35:1--35:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.35},
URN = {urn:nbn:de:0030-drops-138343},
doi = {10.4230/LIPIcs.SoCG.2021.35},
annote = {Keywords: Lenses, Circles, Polynomial partitioning, Incidences}
}
Document
Packing Squares into a Disk with Optimal Worst-Case Density
Abstract
We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is δ = 8/(5π)≈ 0.509. This implies that any set of (not necessarily equal) squares of total area A ≤ 8/5 can always be packed into a disk with radius 1; in contrast, for any ε > 0 there are sets of squares of total area 8/5+ε that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square (1/2), circles in a square (π/(3+2√2) ≈ 0.539) and circles in a circle (1/2) have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.
Cite as
Sándor P. Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist, and Christian Scheffer. Packing Squares into a Disk with Optimal Worst-Case Density. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{fekete_et_al:LIPIcs.SoCG.2021.36,
author = {Fekete, S\'{a}ndor P. and Gurunathan, Vijaykrishna and Juneja, Kushagra and Keldenich, Phillip and Kleist, Linda and Scheffer, Christian},
title = {{Packing Squares into a Disk with Optimal Worst-Case Density}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {36:1--36:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.36},
URN = {urn:nbn:de:0030-drops-138356},
doi = {10.4230/LIPIcs.SoCG.2021.36},
annote = {Keywords: Square packing, packing density, tight worst-case bound, interval arithmetic, approximation}
}
Document
Sunflowers in Set Systems of Bounded Dimension
Abstract
Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if |F| ≥ c^k, then F contains an r-sunflower.
We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) ≤ d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function.
We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.
Cite as
Jacob Fox, János Pach, and Andrew Suk. Sunflowers in Set Systems of Bounded Dimension. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{fox_et_al:LIPIcs.SoCG.2021.37,
author = {Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
title = {{Sunflowers in Set Systems of Bounded Dimension}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {37:1--37:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.37},
URN = {urn:nbn:de:0030-drops-138366},
doi = {10.4230/LIPIcs.SoCG.2021.37},
annote = {Keywords: Sunflower, VC-dimension, Littlestone dimension, pseudodisks}
}
Document
Strong Hanani-Tutte for the Torus
Abstract
If a graph can be drawn on the torus so that every two independent edges cross an even number of times, then the graph can be embedded on the torus.
Cite as
Radoslav Fulek, Michael J. Pelsmajer, and Marcus Schaefer. Strong Hanani-Tutte for the Torus. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{fulek_et_al:LIPIcs.SoCG.2021.38,
author = {Fulek, Radoslav and Pelsmajer, Michael J. and Schaefer, Marcus},
title = {{Strong Hanani-Tutte for the Torus}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {38:1--38:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.38},
URN = {urn:nbn:de:0030-drops-138378},
doi = {10.4230/LIPIcs.SoCG.2021.38},
annote = {Keywords: Graph Embedding, Torus, Hanani-Tutte Theorem, Intersection Form}
}
Document
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
Abstract
In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9+ε < 1.89 and there is a (3/2+ε)-approximation algorithm if we are allowed to rotate items by 90 degrees [Gálvez et al., FOCS 2017]. In this paper, we give (4/3+ε)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers polynomially bounded in n.
Gálvez et al.’s algorithm for 2DK partitions the knapsack into a constant number of rectangular regions plus one L-shaped region and packs items into those in a structured way. We generalize this approach by allowing up to a constant number of more general regions that can have the shape of an L, a U, a Z, a spiral, and more, and therefore obtain an improved approximation ratio. In particular, we present an algorithm that computes the essentially optimal structured packing into these regions.
Cite as
Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese. Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{galvez_et_al:LIPIcs.SoCG.2021.39,
author = {G\'{a}lvez, Waldo and Grandoni, Fabrizio and Khan, Arindam and Ram{\'\i}rez-Romero, Diego and Wiese, Andreas},
title = {{Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {39:1--39:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.39},
URN = {urn:nbn:de:0030-drops-138386},
doi = {10.4230/LIPIcs.SoCG.2021.39},
annote = {Keywords: Approximation algorithms, two-dimensional knapsack, geometric packing}
}
Document
A Stepping-Up Lemma for Topological Set Systems
Abstract
Intersection patterns of convex sets in ℝ^d have the remarkable property that for d+1 ≤ k ≤ 𝓁, in any sufficiently large family of convex sets in ℝ^d, if a constant fraction of the k-element subfamilies have nonempty intersection, then a constant fraction of the 𝓁-element subfamilies must also have nonempty intersection. Here, we prove that a similar phenomenon holds for any topological set system ℱ in ℝ^d. Quantitatively, our bounds depend on how complicated the intersection of 𝓁 elements of ℱ can be, as measured by the maximum of the ⌈d/2⌉ first Betti numbers. As an application, we improve the fractional Helly number of set systems with bounded topological complexity due to the third author, from a Ramsey number down to d+1. We also shed some light on a conjecture of Kalai and Meshulam on intersection patterns of sets with bounded homological VC dimension. A key ingredient in our proof is the use of the stair convexity of Bukh, Matoušek and Nivasch to recast a simplicial complex as a homological minor of a cubical complex.
Cite as
Xavier Goaoc, Andreas F. Holmsen, and Zuzana Patáková. A Stepping-Up Lemma for Topological Set Systems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{goaoc_et_al:LIPIcs.SoCG.2021.40,
author = {Goaoc, Xavier and Holmsen, Andreas F. and Pat\'{a}kov\'{a}, Zuzana},
title = {{A Stepping-Up Lemma for Topological Set Systems}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {40:1--40:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.40},
URN = {urn:nbn:de:0030-drops-138396},
doi = {10.4230/LIPIcs.SoCG.2021.40},
annote = {Keywords: Helly-type theorem, Topological combinatorics, Homological minors, Stair convexity, Cubical complexes, Homological VC dimension, Ramsey-type theorem}
}
Document
Throwing a Sofa Through the Window
Abstract
We study several variants of the problem of moving a convex polytope K, with n edges, in three dimensions through a flat rectangular (and sometimes more general) window. Specifically:
ii) We study variants where the motion is restricted to translations only, discuss situations where such a motion can be reduced to sliding (translation in a fixed direction), and present efficient algorithms for those variants, which run in time close to O(n^{8/3}).
iii) We consider the case of a gate (an unbounded window with two parallel infinite edges), and show that K can pass through such a window, by any collision-free rigid motion, iff it can slide through it, an observation that leads to an efficient algorithm for this variant too.
iv) We consider arbitrary compact convex windows, and show that if K can pass through such a window W (by any motion) then K can slide through a slab of width equal to the diameter of W.
v) We show that if a purely translational motion for K through a rectangular window W exists, then K can also slide through W keeping the same orientation as in the translational motion. For a given fixed orientation of K we can determine in linear time whether K can translate (and hence slide) through W keeping the given orientation, and if so plan the motion, also in linear time.
vi) We give an example of a polytope that cannot pass through a certain window by translations only, but can do so when rotations are allowed.
vii) We study the case of a circular window W, and show that, for the regular tetrahedron K of edge length 1, there are two thresholds 1 > δ₁≈ 0.901388 > δ₂≈ 0.895611, such that (a) K can slide through W if the diameter d of W is ≥ 1, (b) K cannot slide through W but can pass through it by a purely translational motion when δ₁ ≤ d < 1, (c) K cannot pass through W by a purely translational motion but can do it when rotations are allowed when δ₂ ≤ d < δ₁, and (d) K cannot pass through W at all when d < δ₂.
viii) Finally, we explore the general setup, where we want to plan a general motion (with all six degrees of freedom) for K through a rectangular window W, and present an efficient algorithm for this problem, with running time close to O(n⁴).
Cite as
Dan Halperin, Micha Sharir, and Itay Yehuda. Throwing a Sofa Through the Window. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{halperin_et_al:LIPIcs.SoCG.2021.41,
author = {Halperin, Dan and Sharir, Micha and Yehuda, Itay},
title = {{Throwing a Sofa Through the Window}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {41:1--41:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.41},
URN = {urn:nbn:de:0030-drops-138409},
doi = {10.4230/LIPIcs.SoCG.2021.41},
annote = {Keywords: Motion planning, Convex polytopes in 3D}
}
Document
Stabbing Convex Bodies with Lines and Flats
Abstract
We study the problem of constructing weak ε-nets where the stabbing elements are lines or k-flats instead of points. We study this problem in the simplest setting where it is still interesting - namely, the uniform measure of volume over the hypercube [0,1]^d. Specifically, a (k,ε)-net is a set of k-flats, such that any convex body in [0,1]^d of volume larger than ε is stabbed by one of these k-flats. We show that for k ≥ 1, one can construct (k,ε)-nets of size O(1/ε^{1-k/d}). We also prove that any such net must have size at least Ω(1/ε^{1-k/d}). As a concrete example, in three dimensions all ε-heavy bodies in [0,1]³ can be stabbed by Θ(1/ε^{2/3}) lines. Note, that these bounds are sublinear in 1/ε, and are thus somewhat surprising.
Cite as
Sariel Har-Peled and Mitchell Jones. Stabbing Convex Bodies with Lines and Flats. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{harpeled_et_al:LIPIcs.SoCG.2021.42,
author = {Har-Peled, Sariel and Jones, Mitchell},
title = {{Stabbing Convex Bodies with Lines and Flats}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {42:1--42:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.42},
URN = {urn:nbn:de:0030-drops-138412},
doi = {10.4230/LIPIcs.SoCG.2021.42},
annote = {Keywords: Discrete geometry, combinatorics, weak \epsilon-nets, k-flats}
}
Document
Reliable Spanners for Metric Spaces
Abstract
A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation, that is, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees and (general) metric spaces.
Cite as
Sariel Har-Peled, Manor Mendel, and Dániel Oláh. Reliable Spanners for Metric Spaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{harpeled_et_al:LIPIcs.SoCG.2021.43,
author = {Har-Peled, Sariel and Mendel, Manor and Ol\'{a}h, D\'{a}niel},
title = {{Reliable Spanners for Metric Spaces}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {43:1--43:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.43},
URN = {urn:nbn:de:0030-drops-138423},
doi = {10.4230/LIPIcs.SoCG.2021.43},
annote = {Keywords: Spanners, reliability}
}
Document
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
Abstract
Given a closed simple polygon P, we say two points p,q see each other if the segment seg(p,q) is fully contained in P. The art gallery problem seeks a minimum size set G ⊂ P of guards that sees P completely. The only currently correct algorithm to solve the art gallery problem exactly uses algebraic methods. As the art gallery problem is ∃ ℝ-complete, it seems unlikely to avoid algebraic methods, for any exact algorithm, without additional assumptions.
In this paper, we introduce the notion of vision-stability. In order to describe vision-stability consider an enhanced guard that can see "around the corner" by an angle of δ or a diminished guard whose vision is by an angle of δ "blocked" by reflex vertices. A polygon P has vision-stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot vision-stable algorithm that computes an optimal guard set for vision-stable polygons using polynomial time and solving one integer program. It guarantees to find the optimal solution for every vision-stable polygon. We implemented an iterative vision-stable algorithm and show its practical performance is slower, but comparable with other state-of-the-art algorithms. The practical implementation can be found at: https://github.com/simonheng/AGPIterative. Our iterative algorithm is inspired and follows closely the one-shot algorithm. It delays several steps and only computes them when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-visibility width (cw(P)) of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admit an FPT algorithm when parameterized by the chord-visibility width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices.
Cite as
Simon B. Hengeveld and Tillmann Miltzow. A Practical Algorithm with Performance Guarantees for the Art Gallery Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 44:1-44:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{hengeveld_et_al:LIPIcs.SoCG.2021.44,
author = {Hengeveld, Simon B. and Miltzow, Tillmann},
title = {{A Practical Algorithm with Performance Guarantees for the Art Gallery Problem}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {44:1--44:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.44},
URN = {urn:nbn:de:0030-drops-138433},
doi = {10.4230/LIPIcs.SoCG.2021.44},
annote = {Keywords: Art Gallery, Parametrized complexity, Integer Programming, Visibility}
}
Document
Approximate Range Counting Under Differential Privacy
Abstract
Range counting under differential privacy has been studied extensively. Unfortunately, lower bounds based on discrepancy theory suggest that large errors have to be introduced in order to preserve privacy: Essentially for any range space (except axis-parallel rectangles), the error has to be polynomial. In this paper, we show that by allowing a standard notion of geometric approximation where points near the boundary of the range may or may not be counted, the error can be reduced to logarithmic. Furthermore, our approximate range counting data structure can be used to solve the approximate nearest neighbor (ANN) problem and k-NN classification, leading to the first differentially private algorithms for these two problems with provable guarantees on the utility.
Cite as
Ziyue Huang and Ke Yi. Approximate Range Counting Under Differential Privacy. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{huang_et_al:LIPIcs.SoCG.2021.45,
author = {Huang, Ziyue and Yi, Ke},
title = {{Approximate Range Counting Under Differential Privacy}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {45:1--45:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.45},
URN = {urn:nbn:de:0030-drops-138441},
doi = {10.4230/LIPIcs.SoCG.2021.45},
annote = {Keywords: Differential Privacy, Approximate Range Counting}
}
Document
Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs
Abstract
We consider the problem of computing shortest paths in weighted unit-disk graphs in constant dimension d. Although the single-source and all-pairs variants of this problem are well-studied in the plane case, no non-trivial exact distance oracles for unit-disk graphs have been known to date, even for d = 2.
The classical result of Sedgewick and Vitter [Algorithmica '86] shows that for weighted unit-disk graphs in the plane the A^* search has average-case performance superior to that of a standard shortest path algorithm, e.g., Dijkstra’s algorithm. Specifically, if the n corresponding points of a weighted unit-disk graph G are picked from a unit square uniformly at random, and the connectivity radius is r ∈ (0,1), A^* finds a shortest path in G in O(n) expected time when r = Ω(√{log n/n}), even though G has Θ((nr)²) edges in expectation. In other words, the work done by the algorithm is in expectation proportional to the number of vertices and not the number of edges.
In this paper, we break this natural barrier and show even stronger sublinear time results. We propose a new heuristic approach to computing point-to-point exact shortest paths in unit-disk graphs. We analyze the average-case behavior of our heuristic using the same random graph model as used by Sedgewick and Vitter and prove it superior to A^*. Specifically, we show that, if we are able to report the set of all k points of G from an arbitrary rectangular region of the plane in O(k + t(n)) time, then a shortest path between arbitrary two points of such a random graph on the plane can be found in O(1/r² + t(n)) expected time. In particular, the state-of-the-art range reporting data structures imply a sublinear expected bound for all r = Ω(√{log n/n}) and O(√n) expected bound for r = Ω(n^{-1/4}) after only near-linear preprocessing of the point set.
Our approach naturally generalizes to higher dimensions d ≥ 3 and yields sublinear expected bounds for all d = O(1) and sufficiently large r.
Cite as
Adam Karczmarz, Jakub Pawlewicz, and Piotr Sankowski. Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{karczmarz_et_al:LIPIcs.SoCG.2021.46,
author = {Karczmarz, Adam and Pawlewicz, Jakub and Sankowski, Piotr},
title = {{Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {46:1--46:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.46},
URN = {urn:nbn:de:0030-drops-138454},
doi = {10.4230/LIPIcs.SoCG.2021.46},
annote = {Keywords: unit-disk graphs, shortest paths, distance oracles}
}
Document
No Krasnoselskii Number for General Sets
Abstract
For a family ℱ of non-empty sets in ℝ^d, the Krasnoselskii number of ℱ is the smallest m such that for any S ∈ ℱ, if every m or fewer points of S are visible from a common point in S, then any finite subset of S is visible from a single point. More than 35 years ago, Peterson asked whether there exists a Krasnoselskii number for general sets in ℝ^d. The best known positive result is Krasnoselskii number 3 for closed sets in the plane, and the best known negative result is that if a Krasnoselskii number for general sets in ℝ^d exists, it cannot be smaller than (d+1)².
In this paper we answer Peterson’s question in the negative by showing that there is no Krasnoselskii number for the family of all sets in ℝ². The proof is non-constructive, and uses transfinite induction and the well-ordering theorem.
In addition, we consider Krasnoselskii numbers with respect to visibility through polygonal paths of length ≤ n, for which an analogue of Krasnoselskii’s theorem for compact simply connected sets was proved by Magazanik and Perles. We show, by an explicit construction, that for any n ≥ 2, there is no Krasnoselskii number for the family of compact sets in ℝ² with respect to visibility through paths of length ≤ n. (Here the counterexamples are finite unions of line segments.)
Cite as
Chaya Keller and Micha A. Perles. No Krasnoselskii Number for General Sets. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 47:1-47:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{keller_et_al:LIPIcs.SoCG.2021.47,
author = {Keller, Chaya and Perles, Micha A.},
title = {{No Krasnoselskii Number for General Sets}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {47:1--47:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.47},
URN = {urn:nbn:de:0030-drops-138462},
doi = {10.4230/LIPIcs.SoCG.2021.47},
annote = {Keywords: visibility, Helly-type theorems, Krasnoselskii’s theorem, transfinite induction, well-ordering theorem}
}
Document
On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem
Abstract
In two-dimensional geometric knapsack problem, we are given a set of n axis-aligned rectangular items and an axis-aligned square-shaped knapsack. Each item has integral width, integral height and an associated integral profit. The goal is to find a (non-overlapping axis-aligned) packing of a maximum profit subset of rectangles into the knapsack. A well-studied and frequently used constraint in practice is to allow only packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts that do not intersect any item of the solution. In this paper we study approximation algorithms for the geometric knapsack problem under guillotine cut constraints. We present polynomial time (1+ε)-approximation algorithms for the cases with and without allowing rotations by 90 degrees, assuming that all input numeric data are polynomially bounded in n. In comparison, the best-known approximation factor for this setting is 3+ε [Jansen-Zhang, SODA 2004], even in the cardinality case where all items have the same profit.
Our main technical contribution is a structural lemma which shows that any guillotine packing can be converted into another structured guillotine packing with almost the same profit. In this packing, each item is completely contained in one of a constant number of boxes and 𝖫-shaped regions, inside which the items are placed by a simple greedy routine. In particular, we provide a clean sufficient condition when such a packing obeys the guillotine cut constraints which might be useful for other settings where these constraints are imposed.
Cite as
Arindam Khan, Arnab Maiti, Amatya Sharma, and Andreas Wiese. On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{khan_et_al:LIPIcs.SoCG.2021.48,
author = {Khan, Arindam and Maiti, Arnab and Sharma, Amatya and Wiese, Andreas},
title = {{On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {48:1--48:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.48},
URN = {urn:nbn:de:0030-drops-138474},
doi = {10.4230/LIPIcs.SoCG.2021.48},
annote = {Keywords: Approximation Algorithms, Multidimensional Knapsack, Guillotine Cuts, Geometric Packing, Rectangle Packing}
}
Document
Restricted Constrained Delaunay Triangulations
Abstract
We introduce the restricted constrained Delaunay triangulation (restricted CDT), a generalization of both the restricted Delaunay triangulation and the constrained Delaunay triangulation. The restricted CDT is a triangulation of a surface whose edges include a set of user-specified constraining segments. We define the restricted CDT to be the dual of a restricted Voronoi diagram defined on a surface that we have extended by topological surgery. We prove several properties of restricted CDTs, including sampling conditions under which the restricted CDT contains every constraining segment and is homeomorphic to the underlying surface.
Cite as
Marc Khoury and Jonathan Richard Shewchuk. Restricted Constrained Delaunay Triangulations. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{khoury_et_al:LIPIcs.SoCG.2021.49,
author = {Khoury, Marc and Shewchuk, Jonathan Richard},
title = {{Restricted Constrained Delaunay Triangulations}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {49:1--49:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.49},
URN = {urn:nbn:de:0030-drops-138481},
doi = {10.4230/LIPIcs.SoCG.2021.49},
annote = {Keywords: restricted Delaunay triangulation, constrained Delaunay triangulation, surface meshing, surface reconstruction, topological surgery, portals}
}
Document
Near Neighbor Search via Efficient Average Distortion Embeddings
Abstract
A recent series of papers by Andoni, Naor, Nikolov, Razenshteyn, and Waingarten (STOC 2018, FOCS 2018) has given approximate near neighbour search (NNS) data structures for a wide class of distance metrics, including all norms. In particular, these data structures achieve approximation on the order of p for 𝓁_p^d norms with space complexity nearly linear in the dataset size n and polynomial in the dimension d, and query time sub-linear in n and polynomial in d. The main shortcoming is the exponential in d pre-processing time required for their construction.
In this paper, we describe a more direct framework for constructing NNS data structures for general norms. More specifically, we show via an algorithmic reduction that an efficient NNS data structure for a metric ℳ is implied by an efficient average distortion embedding of ℳ into 𝓁₁ or the Euclidean space. In particular, the resulting data structures require only polynomial pre-processing time, as long as the embedding can be computed in polynomial time.
As a concrete instantiation of this framework, we give an NNS data structure for 𝓁_p with efficient pre-processing that matches the approximation factor, space and query complexity of the aforementioned data structure of Andoni et al. On the way, we resolve a question of Naor (Analysis and Geometry in Metric Spaces, 2014) and provide an explicit, efficiently computable embedding of 𝓁_p, for p ≥ 1, into 𝓁₁ with average distortion on the order of p. Furthermore, we also give data structures for Schatten-p spaces with improved space and query complexity, albeit still requiring exponential pre-processing when p ≥ 2. We expect our approach to pave the way for constructing efficient NNS data structures for all norms.
Cite as
Deepanshu Kush, Aleksandar Nikolov, and Haohua Tang. Near Neighbor Search via Efficient Average Distortion Embeddings. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{kush_et_al:LIPIcs.SoCG.2021.50,
author = {Kush, Deepanshu and Nikolov, Aleksandar and Tang, Haohua},
title = {{Near Neighbor Search via Efficient Average Distortion Embeddings}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {50:1--50:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.50},
URN = {urn:nbn:de:0030-drops-138490},
doi = {10.4230/LIPIcs.SoCG.2021.50},
annote = {Keywords: Nearest neighbor search, metric space embeddings, average distortion embeddings, locality-sensitive hashing}
}
Document
Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast
Abstract
The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to 1971. In each step of the Gibbs Sampler, we pick a random coordinate and re-sample that coordinate from the distribution induced by fixing all the other coordinates. While it has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that for a convex body K in ℝⁿ with diameter D, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on K is polynomial in n and D. We also give a lower bound on the mixing rate of CHAR, showing that it is strictly worse than hit-and-run and the ball walk in the worst case.
Cite as
Aditi Laddha and Santosh S. Vempala. Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{laddha_et_al:LIPIcs.SoCG.2021.51,
author = {Laddha, Aditi and Vempala, Santosh S.},
title = {{Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {51:1--51:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.51},
URN = {urn:nbn:de:0030-drops-138503},
doi = {10.4230/LIPIcs.SoCG.2021.51},
annote = {Keywords: Gibbs Sampler, Coordinate Hit and run, Mixing time of Markov Chain}
}
Document
Combinatorial Resultants in the Algebraic Rigidity Matroid
Abstract
Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid CM_n associated to the Cayley-Menger ideal for n points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from K₄ graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we implemented our algorithm in Mathematica: it took less than 15 seconds on an example where a Gröbner Basis calculation took 5 days and 6 hrs.
Cite as
Goran Malić and Ileana Streinu. Combinatorial Resultants in the Algebraic Rigidity Matroid. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{malic_et_al:LIPIcs.SoCG.2021.52,
author = {Mali\'{c}, Goran and Streinu, Ileana},
title = {{Combinatorial Resultants in the Algebraic Rigidity Matroid}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {52:1--52:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.52},
URN = {urn:nbn:de:0030-drops-138514},
doi = {10.4230/LIPIcs.SoCG.2021.52},
annote = {Keywords: Cayley-Menger ideal, rigidity matroid, circuit polynomial, combinatorial resultant, inductive construction, Gr\"{o}bner basis elimination}
}
Document
Parameterized Complexity of Quantum Knot Invariants
Abstract
We give a general fixed parameter tractable algorithm to compute quantum invariants of links presented by planar diagrams, whose complexity is singly exponential in the carving-width (or the tree-width) of the diagram.
In particular, we get a O(N^{3/2 cw} poly(n)) ∈ N^O(√n) time algorithm to compute any Reshetikhin-Turaev invariant - derived from a simple Lie algebra 𝔤 - of a link presented by a planar diagram with n crossings and carving-width cw, and whose components are coloured with 𝔤-modules of dimension at most N. For example, this includes the N^{th}-coloured Jones polynomial.
Cite as
Clément Maria. Parameterized Complexity of Quantum Knot Invariants. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{maria:LIPIcs.SoCG.2021.53,
author = {Maria, Cl\'{e}ment},
title = {{Parameterized Complexity of Quantum Knot Invariants}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {53:1--53:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.53},
URN = {urn:nbn:de:0030-drops-138527},
doi = {10.4230/LIPIcs.SoCG.2021.53},
annote = {Keywords: computational knot theory, parameterized complexity, quantum invariants}
}
Document
Efficient Generation of Rectangulations via Permutation Languages
Abstract
A generic rectangulation is a partition of a rectangle into finitely many interior-disjoint rectangles, such that no four rectangles meet in a point. In this work we present a versatile algorithmic framework for exhaustively generating a large variety of different classes of generic rectangulations. Our algorithms work under very mild assumptions, and apply to a large number of rectangulation classes known from the literature, such as generic rectangulations, diagonal rectangulations, 1-sided/area-universal, block-aligned rectangulations, and their guillotine variants. They also apply to classes of rectangulations that are characterized by avoiding certain patterns, and in this work we initiate a systematic investigation of pattern avoidance in rectangulations. Our generation algorithms are efficient, in some cases even loopless or constant amortized time, i.e., each new rectangulation is generated in constant time in the worst case or on average, respectively. Moreover, the Gray codes we obtain are cyclic, and sometimes provably optimal, in the sense that they correspond to a Hamilton cycle on the skeleton of an underlying polytope. These results are obtained by encoding rectangulations as permutations, and by applying our recently developed permutation language framework.
Cite as
Arturo Merino and Torsten Mütze. Efficient Generation of Rectangulations via Permutation Languages. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{merino_et_al:LIPIcs.SoCG.2021.54,
author = {Merino, Arturo and M\"{u}tze, Torsten},
title = {{Efficient Generation of Rectangulations via Permutation Languages}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {54:1--54:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.54},
URN = {urn:nbn:de:0030-drops-138534},
doi = {10.4230/LIPIcs.SoCG.2021.54},
annote = {Keywords: Exhaustive generation, Gray code, flip graph, polytope, generic rectangulation, diagonal rectangulation, cartogram, floorplan, permutation pattern}
}
Document
Polygon-Universal Graphs
Abstract
We study a fundamental question from graph drawing: given a pair (G,C) of a graph G and a cycle C in G together with a simple polygon P, is there a straight-line drawing of G inside P which maps C to P? We say that such a drawing of (G,C) respects P. We fully characterize those instances (G,C) which are polygon-universal, that is, they have a drawing that respects P for any simple (not necessarily convex) polygon P. Specifically, we identify two necessary conditions for an instance to be polygon-universal. Both conditions are based purely on graph and cycle distances and are easy to check. We show that these two conditions are also sufficient. Furthermore, if an instance (G,C) is planar, that is, if there exists a planar drawing of G with C on the outer face, we show that the same conditions guarantee for every simple polygon P the existence of a planar drawing of (G,C) that respects P. If (G,C) is polygon-universal, then our proofs directly imply a linear-time algorithm to construct a drawing that respects a given polygon P.
Cite as
Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek. Polygon-Universal Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{ophelders_et_al:LIPIcs.SoCG.2021.55,
author = {Ophelders, Tim and Rutter, Ignaz and Speckmann, Bettina and Verbeek, Kevin},
title = {{Polygon-Universal Graphs}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {55:1--55:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.55},
URN = {urn:nbn:de:0030-drops-138540},
doi = {10.4230/LIPIcs.SoCG.2021.55},
annote = {Keywords: Graph drawing, partial drawing extension, simple polygon}
}
Document
On Rich Points and Incidences with Restricted Sets of Lines in 3-Space
Abstract
Let L be a set of n lines in ℝ³ that is contained, when represented as points in the four-dimensional Plücker space of lines in ℝ³, in an irreducible variety T of constant degree which is non-degenerate with respect to L (see below). We show:
(1) If T is two-dimensional, the number of r-rich points (points incident to at least r lines of L) is O(n^{4/3+ε}/r²), for r ⩾ 3 and for any ε > 0, and, if at most n^{1/3} lines of L lie on any common regulus, there are at most O(n^{4/3+ε}) 2-rich points. For r larger than some sufficiently large constant, the number of r-rich points is also O(n/r).
As an application, we deduce (with an ε-loss in the exponent) the bound obtained by Pach and de Zeeuw [J. Pach and F. de Zeeuw, 2017] on the number of distinct distances determined by n points on an irreducible algebraic curve of constant degree in the plane that is not a line nor a circle.
(2) If T is two-dimensional, the number of incidences between L and a set of m points in ℝ³ is O(m+n).
(3) If T is three-dimensional and nonlinear, the number of incidences between L and a set of m points in ℝ³ is O (m^{3/5}n^{3/5} + (m^{11/15}n^{2/5} + m^{1/3}n^{2/3})s^{1/3} + m + n), provided that no plane contains more than s of the points. When s = O(min{n^{3/5}/m^{2/5}, m^{1/2}}), the bound becomes O(m^{3/5}n^{3/5}+m+n).
As an application, we prove that the number of incidences between m points and n lines in ℝ⁴ contained in a quadratic hypersurface (which does not contain a hyperplane) is O(m^{3/5}n^{3/5} + m + n).
The proofs use, in addition to various tools from algebraic geometry, recent bounds on the number of incidences between points and algebraic curves in the plane.
Cite as
Micha Sharir and Noam Solomon. On Rich Points and Incidences with Restricted Sets of Lines in 3-Space. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{sharir_et_al:LIPIcs.SoCG.2021.56,
author = {Sharir, Micha and Solomon, Noam},
title = {{On Rich Points and Incidences with Restricted Sets of Lines in 3-Space}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {56:1--56:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.56},
URN = {urn:nbn:de:0030-drops-138551},
doi = {10.4230/LIPIcs.SoCG.2021.56},
annote = {Keywords: Lines in space, Rich points, Polynomial partitioning, Incidences}
}
Document
Sketching Persistence Diagrams
Abstract
Given a persistence diagram with n points, we give an algorithm that produces a sequence of n persistence diagrams converging in bottleneck distance to the input diagram, the ith of which has i distinct (weighted) points and is a 2-approximation to the closest persistence diagram with that many distinct points. For each approximation, we precompute the optimal matching between the ith and the (i+1)st. Perhaps surprisingly, the entire sequence of diagrams as well as the sequence of matchings can be represented in O(n) space. The main approach is to use a variation of the greedy permutation of the persistence diagram to give good Hausdorff approximations and assign weights to these subsets. We give a new algorithm to efficiently compute this permutation, despite the high implicit dimension of points in a persistence diagram due to the effect of the diagonal. The sketches are also structured to permit fast (linear time) approximations to the Hausdorff distance between diagrams - a lower bound on the bottleneck distance. For approximating the bottleneck distance, sketches can also be used to compute a linear-size neighborhood graph directly, obviating the need for geometric data structures used in state-of-the-art methods for bottleneck computation.
Cite as
Donald R. Sheehy and Siddharth Sheth. Sketching Persistence Diagrams. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{sheehy_et_al:LIPIcs.SoCG.2021.57,
author = {Sheehy, Donald R. and Sheth, Siddharth},
title = {{Sketching Persistence Diagrams}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {57:1--57:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.57},
URN = {urn:nbn:de:0030-drops-138569},
doi = {10.4230/LIPIcs.SoCG.2021.57},
annote = {Keywords: Bottleneck Distance, Persistent Homology, Approximate Persistence Diagrams}
}
Document
A Sparse Delaunay Filtration
Abstract
We show how a filtration of Delaunay complexes can be used to approximate the persistence diagram of the distance to a point set in ℝ^d. Whereas the full Delaunay complex can be used to compute this persistence diagram exactly, it may have size O(n^⌈d/2⌉). In contrast, our construction uses only O(n) simplices. The central idea is to connect Delaunay complexes on progressively denser subsamples by considering the flips in an incremental construction as simplices in d+1 dimensions. This approach leads to a very simple and straightforward proof of correctness in geometric terms, because the final filtration is dual to a (d+1)-dimensional Voronoi construction similar to the standard Delaunay filtration. We also, show how this complex can be efficiently constructed.
Cite as
Donald R. Sheehy. A Sparse Delaunay Filtration. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{sheehy:LIPIcs.SoCG.2021.58,
author = {Sheehy, Donald R.},
title = {{A Sparse Delaunay Filtration}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {58:1--58:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.58},
URN = {urn:nbn:de:0030-drops-138579},
doi = {10.4230/LIPIcs.SoCG.2021.58},
annote = {Keywords: Delaunay Triangulation, Persistent Homology, Sparse Filtrations}
}
Document
An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons
Abstract
Given a set S of m point sites in a simple polygon P of n vertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram for S in P. It is known that the problem has an Ω(n+mlog m) time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in O(n+mlog m) expected time. The previous best deterministic algorithms solve the problem in O(nlog log n+ mlog m) time [Oh, Barba, and Ahn, SoCG 2016] or in O(n+mlog m+mlog² n) time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of O(n+mlog m) time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.
Cite as
Haitao Wang. An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{wang:LIPIcs.SoCG.2021.59,
author = {Wang, Haitao},
title = {{An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {59:1--59:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.59},
URN = {urn:nbn:de:0030-drops-138585},
doi = {10.4230/LIPIcs.SoCG.2021.59},
annote = {Keywords: farthest-sites, Voronoi diagrams, triple-point geodesic center, simple polygons}
}
Document
A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem
Abstract
We propose a theoretically-efficient and practical parallel batch-dynamic data structure for the closest pair problem. Our solution is based on a serial dynamic closest pair data structure by Golin et al., and supports batches of insertions and deletions in parallel. For a data set of size n, our data structure supports a batch of insertions or deletions of size m in O(m(1+log ((n+m)/m))) expected work and O(log (n+m)log^*(n+m)) depth with high probability, and takes linear space. The key techniques for achieving these bounds are a new work-efficient parallel batch-dynamic binary heap, and careful management of the computation across sets of points to minimize work and depth.
We provide an optimized multicore implementation of our data structure using dynamic hash tables, parallel heaps, and dynamic k-d trees. Our experiments on a variety of synthetic and real-world data sets show that it achieves a parallel speedup of up to 38.57x (15.10x on average) on 48 cores with hyper-threading. In addition, we also implement and compare four parallel algorithms for static closest pair problem, for which we are not aware of any existing practical implementations. On 48 cores with hyper-threading, the static algorithms achieve up to 51.45x (29.42x on average) speedup, and Rabin’s algorithm performs the best on average. Comparing our dynamic algorithm to the fastest static algorithm, we find that it is advantageous to use the dynamic algorithm for batch sizes of up to 20% of the data set. As far as we know, our work is the first to experimentally evaluate parallel closest pair algorithms, in both the static and the dynamic settings.
Cite as
Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{wang_et_al:LIPIcs.SoCG.2021.60,
author = {Wang, Yiqiu and Yu, Shangdi and Gu, Yan and Shun, Julian},
title = {{A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {60:1--60:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.60},
URN = {urn:nbn:de:0030-drops-138594},
doi = {10.4230/LIPIcs.SoCG.2021.60},
annote = {Keywords: Closest Pair, Parallel Algorithms, Dynamic Algorithms, Experimental Algorithms}
}
Document
Media Exposition
An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition)
Abstract
The construction of bounded-degree plane geometric spanners has been a focus of interest in the field of geometric spanners for a long time. To date, several algorithms have been designed with various trade-offs in degree and stretch factor. Using JSXGraph, a state-of-the-art JavaScript library for geometry, we have implemented seven of these sophisticated algorithms so that they can be used for further research and teaching computational geometry. We believe that our interactive tool can be used by researchers from related fields to understand and apply the algorithms in their research. Our tool can be run in any modern browser. The tool will be permanently maintained by the second author at https://ghoshanirban.github.io/bounded-degree-plane-spanners/index.html
Cite as
Fred Anderson, Anirban Ghosh, Matthew Graham, Lucas Mougeot, and David Wisnosky. An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 61:1-61:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{anderson_et_al:LIPIcs.SoCG.2021.61,
author = {Anderson, Fred and Ghosh, Anirban and Graham, Matthew and Mougeot, Lucas and Wisnosky, David},
title = {{An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {61:1--61:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.61},
URN = {urn:nbn:de:0030-drops-138607},
doi = {10.4230/LIPIcs.SoCG.2021.61},
annote = {Keywords: graph approximation, Delaunay triangulations, geometric spanners, plane spanners, bounded-degree spanners}
}
Document
Media Exposition
Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition)
Abstract
We illustrate and animate the classic problem of deciding whether a given graph has an Eulerian path. Starting with a collection of instances of increasing difficulty, we present a set of pictorial instructions, and show how they can be used to solve all instances. These IDEA instructions ("A series of nonverbal algorithm assembly instructions") have proven to be both entertaining for experts and enlightening for novices. We (w)rap up with a song and dance to Euler’s original instance.
Cite as
Aaron T. Becker, Sándor P. Fekete, Matthias Konitzny, Sebastian Morr, and Arne Schmidt. Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 62:1-62:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{becker_et_al:LIPIcs.SoCG.2021.62,
author = {Becker, Aaron T. and Fekete, S\'{a}ndor P. and Konitzny, Matthias and Morr, Sebastian and Schmidt, Arne},
title = {{Can You Walk This? Eulerian Tours and IDEA Instructions}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {62:1--62:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.62},
URN = {urn:nbn:de:0030-drops-138616},
doi = {10.4230/LIPIcs.SoCG.2021.62},
annote = {Keywords: Eulerian tours, algorithms, education, IDEA instructions}
}
Document
CG Challenge
Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge)
Abstract
This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.
Cite as
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 63:1-63:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{crombez_et_al:LIPIcs.SoCG.2021.63,
author = {Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan and Gonzalez-Lorenzo, Aldo and Lafourcade, Pascal and Libralesso, Luc},
title = {{Shadoks Approach to Low-Makespan Coordinated Motion Planning}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {63:1--63:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.63},
URN = {urn:nbn:de:0030-drops-138622},
doi = {10.4230/LIPIcs.SoCG.2021.63},
annote = {Keywords: heuristics, motion planning, digital geometry, shortest path}
}
Document
CG Challenge
Coordinated Motion Planning Through Randomized k-Opt (CG Challenge)
Abstract
This paper examines the approach taken by team gitastrophe in the CG:SHOP 2021 challenge. The challenge was to find a sequence of simultaneous moves of square robots between two given configurations that minimized either total distance travelled or makespan (total time). Our winning approach has two main components: an initialization phase that finds a good initial solution, and a k-opt local search phase which optimizes this solution. This led to a first place finish in the distance category and a third place finish in the makespan category.
Cite as
Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. Coordinated Motion Planning Through Randomized k-Opt (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 64:1-64:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{liu_et_al:LIPIcs.SoCG.2021.64,
author = {Liu, Paul and Spalding-Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
title = {{Coordinated Motion Planning Through Randomized k-Opt}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {64:1--64:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.64},
URN = {urn:nbn:de:0030-drops-138635},
doi = {10.4230/LIPIcs.SoCG.2021.64},
annote = {Keywords: motion planning, randomized local search, path finding}
}
Document
CG Challenge
A Simulated Annealing Approach to Coordinated Motion Planning (CG Challenge)
Abstract
The third computational geometry challenge was on a coordinated motion planning problem in which a collection of square robots need to move on the integer grid, from their given starting points to their target points, and without collision between robots, or between robots and a set of input obstacles. We designed and implemented an algorithm for this problem, which consists of three parts. First, we computed a feasible solution by placing middle-points outside of the minimum bounding box of the input positions of the robots and the obstacles, and moving each robot from its starting point to its target point through a middle-point. Second, we applied a simple local search approach where we repeatedly delete and insert again a random robot through an optimal path. It improves the quality of the solution, as the robots no longer need to go through the middle-points. Finally, we used simulated annealing to further improve this feasible solution. We used two different types of moves: We either tightened the whole trajectory of a robot, or we stretched it between two points by making the robot move through a third intermediate point generated at random.
Cite as
Hyeyun Yang and Antoine Vigneron. A Simulated Annealing Approach to Coordinated Motion Planning (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 65:1-65:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{yang_et_al:LIPIcs.SoCG.2021.65,
author = {Yang, Hyeyun and Vigneron, Antoine},
title = {{A Simulated Annealing Approach to Coordinated Motion Planning}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {65:1--65:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.65},
URN = {urn:nbn:de:0030-drops-138649},
doi = {10.4230/LIPIcs.SoCG.2021.65},
annote = {Keywords: Path planning, simulated annealing, local search}
}