Volume
LIPIcs, Volume 164
36th International Symposium on Computational Geometry (SoCG 2020)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG)
Event
SoCG 2020, June 23-26, 2020, Zürich, SwitzerlandEditors
Publication Details
- published at: 2020-06-08
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-143-6
- DBLP: db/conf/compgeom/compgeom2020
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 164, SoCG 2020, Complete Volume
Abstract
LIPIcs, Volume 164, SoCG 2020, Complete Volume
Cite as
36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1-1222, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@Proceedings{cabello_et_al:LIPIcs.SoCG.2020,
title = {{LIPIcs, Volume 164, SoCG 2020, Complete Volume}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {1--1222},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020},
URN = {urn:nbn:de:0030-drops-121576},
doi = {10.4230/LIPIcs.SoCG.2020},
annote = {Keywords: LIPIcs, Volume 164, SoCG 2020, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{cabello_et_al:LIPIcs.SoCG.2020.0,
author = {Cabello, Sergio and Chen, Danny Z.},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {0:i--0:xx},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.0},
URN = {urn:nbn:de:0030-drops-121587},
doi = {10.4230/LIPIcs.SoCG.2020.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons
Abstract
What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has mn-(m+n)+3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only mn-(m + ⌈ n/6 ⌉), for m ≥ n. We prove a new upper bound of mn-(m+n)+C for some constant C, which is optimal apart from the value of C.
Cite as
Eyal Ackerman, Balázs Keszegh, and Günter Rote. An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{ackerman_et_al:LIPIcs.SoCG.2020.1,
author = {Ackerman, Eyal and Keszegh, Bal\'{a}zs and Rote, G\"{u}nter},
title = {{An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {1:1--1:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.1},
URN = {urn:nbn:de:0030-drops-121591},
doi = {10.4230/LIPIcs.SoCG.2020.1},
annote = {Keywords: Simple polygon, Ramsey theory, combinatorial geometry}
}
Document
Dynamic Geometric Set Cover and Hitting Set
Abstract
We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in ℝ¹ and ℝ². The first framework uses bootstrapping and gives a (1+ε)-approximate data structure for dynamic interval set cover in ℝ¹ with O(n^α/ε) amortized update time for any constant α > 0; in ℝ², this method gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set with O(n^(1/2+α)) amortized update time. The second framework uses local modification, and leads to a (1+ε)-approximate data structure for dynamic interval hitting set in ℝ¹ with Õ(1/ε) amortized update time; in ℝ², it gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set in the partially dynamic settings with Õ(1) amortized update time.
Cite as
Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue. Dynamic Geometric Set Cover and Hitting Set. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2020.2,
author = {Agarwal, Pankaj K. and Chang, Hsien-Chih and Suri, Subhash and Xiao, Allen and Xue, Jie},
title = {{Dynamic Geometric Set Cover and Hitting Set}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {2:1--2:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.2},
URN = {urn:nbn:de:0030-drops-121604},
doi = {10.4230/LIPIcs.SoCG.2020.2},
annote = {Keywords: Geometric set cover, Geometric hitting set, Dynamic data structures}
}
Document
The Parameterized Complexity of Guarding Almost Convex Polygons
Abstract
The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of Art Gallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA'16], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow, SoCG'17], and it may require irrational guards [Abrahamsen et al., SoCG'17]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ℝ-complete [Abrahamsen et al., STOC'18]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP.
Given the first discovery, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016]: Is Art Gallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of Art Gallery, this case can also be viewed as the classic Dominating Set problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-Vertex Art Gallery is solvable in time r^O(r²)n^O(1). Furthermore, our approach extends to assert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-Vertex Art Gallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions.
Cite as
Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{agrawal_et_al:LIPIcs.SoCG.2020.3,
author = {Agrawal, Akanksha and Knudsen, Kristine V. K. and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
title = {{The Parameterized Complexity of Guarding Almost Convex Polygons}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {3:1--3:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.3},
URN = {urn:nbn:de:0030-drops-121614},
doi = {10.4230/LIPIcs.SoCG.2020.3},
annote = {Keywords: Art Gallery, Reflex vertices, Monotone 2-CSP, Parameterized Complexity, Fixed Parameter Tractability}
}
Document
Euclidean TSP in Narrow Strips
Abstract
We investigate how the complexity of {Euclidean TSP} for point sets P inside the strip (-∞,+∞)×[0,δ] depends on the strip width δ. We obtain two main results.
- For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O(n log²n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ ⩽ 2√2, a bound which is best possible.
- We present an algorithm that is fixed-parameter tractable with respect to δ. More precisely, our algorithm has running time 2^{O(√δ)} n² for sparse point sets, where each 1×δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0,n]× [0,δ], it has an expected running time of 2^{O(√δ)} n² + O(n³).
Cite as
Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak. Euclidean TSP in Narrow Strips. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{alkema_et_al:LIPIcs.SoCG.2020.4,
author = {Alkema, Henk and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor},
title = {{Euclidean TSP in Narrow Strips}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {4:1--4:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.4},
URN = {urn:nbn:de:0030-drops-121628},
doi = {10.4230/LIPIcs.SoCG.2020.4},
annote = {Keywords: Computational geometry, Euclidean TSP, bitonic TSP, fixed-parameter tractable algorithms}
}
Document
The ε-t-Net Problem
Abstract
We study a natural generalization of the classical ε-net problem (Haussler - Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ t/n, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least ε n contains a set in S. When t=1, this corresponds to the ε-net problem.
We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O((1+log t)d/ε log 1/ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(1/ε)-sized ε-t-nets.
We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t=1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.
Cite as
Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The ε-t-Net Problem. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{alon_et_al:LIPIcs.SoCG.2020.5,
author = {Alon, Noga and Jartoux, Bruno and Keller, Chaya and Smorodinsky, Shakhar and Yuditsky, Yelena},
title = {{The \epsilon-t-Net Problem}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {5:1--5:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.5},
URN = {urn:nbn:de:0030-drops-121639},
doi = {10.4230/LIPIcs.SoCG.2020.5},
annote = {Keywords: epsilon-nets, geometric hypergraphs, VC-dimension, linear union complexity}
}
Document
Terrain Visibility Graphs: Persistence Is Not Enough
Abstract
In this paper, we consider the Visibility Graph Recognition and Reconstruction problems in the context of terrains. Here, we are given a graph G with labeled vertices v₀, v₁, …, v_{n-1} such that the labeling corresponds with a Hamiltonian path H. G also may contain other edges. We are interested in determining if there is a terrain T with vertices p₀, p₁, …, p_{n-1} such that G is the visibility graph of T and the boundary of T corresponds with H. G is said to be persistent if and only if it satisfies the so-called X-property and Bar-property. It is known that every "pseudo-terrain" has a persistent visibility graph and that every persistent graph is the visibility graph for some pseudo-terrain. The connection is not as clear for (geometric) terrains. It is known that the visibility graph of any terrain T is persistent, but it has been unclear whether every persistent graph G has a terrain T such that G is the visibility graph of T. There actually have been several papers that claim this to be the case (although no formal proof has ever been published), and recent works made steps towards building a terrain reconstruction algorithm for any persistent graph. In this paper, we show that there exists a persistent graph G that is not the visibility graph for any terrain T. This means persistence is not enough by itself to characterize the visibility graphs of terrains, and implies that pseudo-terrains are not stretchable.
Cite as
Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, Sean Soderman, and Qing Wang. Terrain Visibility Graphs: Persistence Is Not Enough. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{ameer_et_al:LIPIcs.SoCG.2020.6,
author = {Ameer, Safwa and Gibson-Lopez, Matt and Krohn, Erik and Soderman, Sean and Wang, Qing},
title = {{Terrain Visibility Graphs: Persistence Is Not Enough}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {6:1--6:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.6},
URN = {urn:nbn:de:0030-drops-121640},
doi = {10.4230/LIPIcs.SoCG.2020.6},
annote = {Keywords: Terrains, Visibility Graph Characterization, Visibility Graph Recognition}
}
Document
On β-Plurality Points in Spatial Voting Games
Abstract
Let V be a set of n points in ℝ^d, called voters. A point p ∈ ℝ^d is a plurality point for V when the following holds: for every q ∈ ℝ^d the number of voters closer to p than to q is at least the number of voters closer to q than to p. Thus, in a vote where each v ∈ V votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal p will not lose against any alternative proposal q. For most voter sets a plurality point does not exist. We therefore introduce the concept of β-plurality points, which are defined similarly to regular plurality points except that the distance of each voter to p (but not to q) is scaled by a factor β, for some constant 0<β⩽1. We investigate the existence and computation of β-plurality points, and obtain the following results.
- Define β^*_d := sup{β : any finite multiset V in ℝ^d admits a β-plurality point}. We prove that β^*₂ = √3/2, and that 1/√d ⩽ β^*_d ⩽ √3/2 for all d⩾3.
- Define β(V) := sup {β : V admits a β-plurality point}. We present an algorithm that, given a voter set V in {ℝ}^d, computes an (1-ε)⋅ β(V) plurality point in time O(n²/ε^(3d-2) ⋅ log(n/ε^(d-1)) ⋅ log²(1/ε)).
Cite as
Boris Aronov, Mark de Berg, Joachim Gudmundsson, and Michael Horton. On β-Plurality Points in Spatial Voting Games. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.7,
author = {Aronov, Boris and de Berg, Mark and Gudmundsson, Joachim and Horton, Michael},
title = {{On \beta-Plurality Points in Spatial Voting Games}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {7:1--7:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.7},
URN = {urn:nbn:de:0030-drops-121651},
doi = {10.4230/LIPIcs.SoCG.2020.7},
annote = {Keywords: Computational geometry, Spatial voting theory, Plurality point, Computational social choice}
}
Document
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets
Abstract
We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets A, B, and C of points in the plane, that satisfy a certain polynomial equation or two equations. The best known instance of such a problem is testing for the existence of a collinear triple of points in A×B×C, a classical 3SUM-hard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decision-tree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decision-tree model, that uses only roughly O(n^(28/15)) constant-degree polynomial sign tests, for the special case where two of the sets lie on one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to any other problem where we seek a triple that satisfies a single polynomial equation, e.g., determining whether A× B× C contains a triple spanning a unit-area triangle.
This result extends recent work by Barba et al. [Luis Barba et al., 2019] and by Chan [Timothy M. Chan, 2020], where all three sets A, B, and C are assumed to be one-dimensional. While there are common features in the high-level approaches, here and in [Luis Barba et al., 2019], the actual analysis in this work becomes more involved and requires new methods and techniques, involving polynomial partitions and other related tools.
As a second application of our technique, we again have three n-point sets A, B, and C in the plane, and we want to determine whether there exists a triple (a,b,c) ∈ A×B×C that simultaneously satisfies two real polynomial equations. For example, this is the setup when testing for the existence of pairs of similar triangles spanned by the input points, in various contexts discussed later in the paper. We show that problems of this kind can be solved with roughly O(n^(24/13)) constant-degree polynomial sign tests. These problems can be extended to higher dimensions in various ways, and we present subquadratic solutions to some of these extensions, in the algebraic decision-tree model.
Cite as
Boris Aronov, Esther Ezra, and Micha Sharir. Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.8,
author = {Aronov, Boris and Ezra, Esther and Sharir, Micha},
title = {{Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {8:1--8:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.8},
URN = {urn:nbn:de:0030-drops-121666},
doi = {10.4230/LIPIcs.SoCG.2020.8},
annote = {Keywords: Algebraic decision tree, Polynomial partition, Collinearity testing, 3SUM-hard problems, Polynomials vanishing on Cartesian products}
}
Document
Extending Drawings of Graphs to Arrangements of Pseudolines
Abstract
In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.
Cite as
Alan Arroyo, Julien Bensmail, and R. Bruce Richter. Extending Drawings of Graphs to Arrangements of Pseudolines. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{arroyo_et_al:LIPIcs.SoCG.2020.9,
author = {Arroyo, Alan and Bensmail, Julien and Richter, R. Bruce},
title = {{Extending Drawings of Graphs to Arrangements of Pseudolines}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {9:1--9:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.9},
URN = {urn:nbn:de:0030-drops-121672},
doi = {10.4230/LIPIcs.SoCG.2020.9},
annote = {Keywords: graphs, graph drawings, geometric graph drawings, arrangements of pseudolines, crossing numbers, stretchability}
}
Document
Dimensionality Reduction for k-Distance Applied to Persistent Homology
Abstract
Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction for this problem, answering an open question of Sheehy [Proc. SoCG, 2014]. We show that any linear transformation that preserves pairwise distances up to a (1±ε) multiplicative factor, must preserve the persistent homology of the Čech filtration up to a factor of (1-ε)^{-1}. Our results also show that the Vietoris-Rips and Delaunay filtrations for the k-distance, as well as the Čech filtration for the approximate k-distance of Buchet et al. are preserved up to a (1±ε) factor.
We also prove extensions of our main theorem, for point sets (i) lying in a region of bounded Gaussian width or (ii) on a low-dimensional manifold, obtaining the target dimension bounds of Lotz [Proc. Roy. Soc. , 2019] and Clarkson [Proc. SoCG, 2008 ] respectively.
Cite as
Shreya Arya, Jean-Daniel Boissonnat, Kunal Dutta, and Martin Lotz. Dimensionality Reduction for k-Distance Applied to Persistent Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{arya_et_al:LIPIcs.SoCG.2020.10,
author = {Arya, Shreya and Boissonnat, Jean-Daniel and Dutta, Kunal and Lotz, Martin},
title = {{Dimensionality Reduction for k-Distance Applied to Persistent Homology}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {10:1--10:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.10},
URN = {urn:nbn:de:0030-drops-121682},
doi = {10.4230/LIPIcs.SoCG.2020.10},
annote = {Keywords: Dimensionality reduction, Johnson-Lindenstrauss lemma, Topological Data Analysis, Persistent Homology, k-distance, distance to measure}
}
Document
Persistent Homology Based Characterization of the Breast Cancer Immune Microenvironment: A Feasibility Study
Abstract
Persistent homology is a common tool of topological data analysis, whose main descriptor, the persistence diagram, aims at computing and encoding the geometry and topology of given datasets. In this article, we present a novel application of persistent homology to characterize the spatial arrangement of immune and epithelial (tumor) cells within the breast cancer immune microenvironment. More specifically, quantitative and robust characterizations are built by computing persistence diagrams out of a staining technique (quantitative multiplex immunofluorescence) which allows us to obtain spatial coordinates and stain intensities on individual cells. The resulting persistence diagrams are evaluated as characteristic biomarkers of cancer subtype and prognostic biomarker of overall survival. For a cohort of approximately 700 breast cancer patients with median 8.5-year clinical follow-up, we show that these persistence diagrams outperform and complement the usual descriptors which capture spatial relationships with nearest neighbor analysis. This provides new insights and possibilities on the general problem of building (topology-based) biomarkers that are characteristic and predictive of cancer subtype, overall survival and response to therapy.
Cite as
Andrew Aukerman, Mathieu Carrière, Chao Chen, Kevin Gardner, Raúl Rabadán, and Rami Vanguri. Persistent Homology Based Characterization of the Breast Cancer Immune Microenvironment: A Feasibility Study. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{aukerman_et_al:LIPIcs.SoCG.2020.11,
author = {Aukerman, Andrew and Carri\`{e}re, Mathieu and Chen, Chao and Gardner, Kevin and Rabad\'{a}n, Ra\'{u}l and Vanguri, Rami},
title = {{Persistent Homology Based Characterization of the Breast Cancer Immune Microenvironment: A Feasibility Study}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {11:1--11:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.11},
URN = {urn:nbn:de:0030-drops-121695},
doi = {10.4230/LIPIcs.SoCG.2020.11},
annote = {Keywords: Topological data analysis, persistence diagrams}
}
Document
Homotopic Curve Shortening and the Affine Curve-Shortening Flow
Abstract
We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent.
We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between "grid peeling" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids.
We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.
Cite as
Sergey Avvakumov and Gabriel Nivasch. Homotopic Curve Shortening and the Affine Curve-Shortening Flow. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{avvakumov_et_al:LIPIcs.SoCG.2020.12,
author = {Avvakumov, Sergey and Nivasch, Gabriel},
title = {{Homotopic Curve Shortening and the Affine Curve-Shortening Flow}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {12:1--12:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.12},
URN = {urn:nbn:de:0030-drops-121708},
doi = {10.4230/LIPIcs.SoCG.2020.12},
annote = {Keywords: affine curve-shortening flow, shortest homotopic path, integer grid, convex-layer decomposition}
}
Document
Empty Squares in Arbitrary Orientation Among Points
Abstract
This paper studies empty squares in arbitrary orientation among a set P of n points in the plane. We prove that the number of empty squares with four contact pairs is between Ω(n) and O(n²), and that these bounds are tight, provided P is in a certain general position. A contact pair of a square is a pair of a point p ∈ P and a side 𝓁 of the square with p ∈ 𝓁. The upper bound O(n²) also applies to the number of empty squares with four contact points, while we construct a point set among which there is no square of four contact points. We then present an algorithm that maintains a combinatorial structure of the L_∞ Voronoi diagram of P, while the axes of the plane continuously rotate by 90 degrees, and simultaneously reports all empty squares with four contact pairs among P in an output-sensitive way within O(slog n) time and O(n) space, where s denotes the number of reported squares. Several new algorithmic results are also obtained: a largest empty square among P and a square annulus of minimum width or minimum area that encloses P over all orientations can be computed in worst-case O(n² log n) time.
Cite as
Sang Won Bae and Sang Duk Yoon. Empty Squares in Arbitrary Orientation Among Points. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bae_et_al:LIPIcs.SoCG.2020.13,
author = {Bae, Sang Won and Yoon, Sang Duk},
title = {{Empty Squares in Arbitrary Orientation Among Points}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {13:1--13:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.13},
URN = {urn:nbn:de:0030-drops-121716},
doi = {10.4230/LIPIcs.SoCG.2020.13},
annote = {Keywords: empty square, arbitrary orientation, Erd\H{o}s - Szekeres problem, L\underline∞ Voronoi diagram, largest empty square problem, square annulus}
}
Document
Holes and Islands in Random Point Sets
Abstract
For d ∈ ℕ, let S be a finite set of points in ℝ^d in general position. A set H of k points from S is a k-hole in S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S. A set I of k points from S is a k-island in S if conv(I) ∩ S = I. Note that each k-hole in S is a k-island in S.
For fixed positive integers d, k and a convex body K in ℝ^d with d-dimensional Lebesgue measure 1, let S be a set of n points chosen uniformly and independently at random from K. We show that the expected number of k-islands in S is in O(n^d). In the case k=d+1, we prove that the expected number of empty simplices (that is, (d+1)-holes) in S is at most 2^(d-1) ⋅ d! ⋅ binom(n,d). Our results improve and generalize previous bounds by Bárány and Füredi [I. Bárány and Z. Füredi, 1987], Valtr [P. Valtr, 1995], Fabila-Monroy and Huemer [Fabila-Monroy and Huemer, 2012], and Fabila-Monroy, Huemer, and Mitsche [Fabila-Monroy et al., 2015].
Cite as
Martin Balko, Manfred Scheucher, and Pavel Valtr. Holes and Islands in Random Point Sets. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{balko_et_al:LIPIcs.SoCG.2020.14,
author = {Balko, Martin and Scheucher, Manfred and Valtr, Pavel},
title = {{Holes and Islands in Random Point Sets}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {14:1--14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.14},
URN = {urn:nbn:de:0030-drops-121722},
doi = {10.4230/LIPIcs.SoCG.2020.14},
annote = {Keywords: stochastic geometry, random point set, Erd\H{o}s-Szekeres type problem, k-hole, k-island, empty polytope, convex position, Horton set}
}
Document
The Reeb Graph Edit Distance Is Universal
Abstract
We consider the setting of Reeb graphs of piecewise linear functions and study distances between them that are stable, meaning that functions which are similar in the supremum norm ought to have similar Reeb graphs. We define an edit distance for Reeb graphs and prove that it is stable and universal, meaning that it provides an upper bound to any other stable distance. In contrast, via a specific construction, we show that the interleaving distance and the functional distortion distance on Reeb graphs are not universal.
Cite as
Ulrich Bauer, Claudia Landi, and Facundo Mémoli. The Reeb Graph Edit Distance Is Universal. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bauer_et_al:LIPIcs.SoCG.2020.15,
author = {Bauer, Ulrich and Landi, Claudia and M\'{e}moli, Facundo},
title = {{The Reeb Graph Edit Distance Is Universal}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {15:1--15:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.15},
URN = {urn:nbn:de:0030-drops-121730},
doi = {10.4230/LIPIcs.SoCG.2020.15},
annote = {Keywords: Reeb graphs, topological descriptors, edit distance, interleaving distance}
}
Document
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages
Abstract
An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar and all optimal 2-planar graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.
Cite as
Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou. Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bekos_et_al:LIPIcs.SoCG.2020.16,
author = {Bekos, Michael A. and Da Lozzo, Giordano and Griesbach, Svenja M. and Gronemann, Martin and Montecchiani, Fabrizio and Raftopoulou, Chrysanthi},
title = {{Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {16:1--16:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.16},
URN = {urn:nbn:de:0030-drops-121749},
doi = {10.4230/LIPIcs.SoCG.2020.16},
annote = {Keywords: Book embeddings, Book thickness, Nonplanar graphs, Planar skeleton}
}
Document
Parallel Computation of Alpha Complexes for Biomolecules
Abstract
The alpha complex, a subset of the Delaunay triangulation, has been extensively used as the underlying representation for biomolecular structures. We propose a GPU-based parallel algorithm for the computation of the alpha complex, which exploits the knowledge of typical spatial distribution and sizes of atoms in a biomolecule. Unlike existing methods, this algorithm does not require prior construction of the Delaunay triangulation. The algorithm computes the alpha complex in two stages. The first stage proceeds in a bottom-up fashion and computes a superset of the edges, triangles, and tetrahedra belonging to the alpha complex. The false positives from this estimation stage are removed in a subsequent pruning stage to obtain the correct alpha complex. Computational experiments on several biomolecules demonstrate the superior performance of the algorithm, up to a factor of 50 when compared to existing methods that are optimized for biomolecules.
Cite as
Talha Bin Masood, Tathagata Ray, and Vijay Natarajan. Parallel Computation of Alpha Complexes for Biomolecules. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{masood_et_al:LIPIcs.SoCG.2020.17,
author = {Masood, Talha Bin and Ray, Tathagata and Natarajan, Vijay},
title = {{Parallel Computation of Alpha Complexes for Biomolecules}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {17:1--17:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.17},
URN = {urn:nbn:de:0030-drops-121758},
doi = {10.4230/LIPIcs.SoCG.2020.17},
annote = {Keywords: Delaunay triangulation, parallel algorithms, biomolecules, GPU}
}
Document
Relative Persistent Homology
Abstract
The alpha complex efficiently computes persistent homology of a point cloud X in Euclidean space when the dimension d is low. Given a subset A of X, relative persistent homology can be computed as the persistent homology of the relative Čech complex Č(X, A). But this is not computationally feasible for larger point clouds X. The aim of this note is to present a method for efficient computation of relative persistent homology in low dimensional Euclidean space. We introduce the relative Delaunay-Čech complex DelČ(X, A) whose homology is the relative persistent homology. It is constructed from the Delaunay complex of an embedding of X in (d+1)-dimensional Euclidean space.
Cite as
Nello Blaser and Morten Brun. Relative Persistent Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 18:1-18:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{blaser_et_al:LIPIcs.SoCG.2020.18,
author = {Blaser, Nello and Brun, Morten},
title = {{Relative Persistent Homology}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {18:1--18:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.18},
URN = {urn:nbn:de:0030-drops-121762},
doi = {10.4230/LIPIcs.SoCG.2020.18},
annote = {Keywords: topological data analysis, relative homology, Delaunay-\v{C}ech complex, alpha complex}
}
Document
Edge Collapse and Persistence of Flag Complexes
Abstract
In this article, we extend the notions of dominated vertex and strong collapse of a simplicial complex as introduced by J. Barmak and E. Miniam. We say that a simplex (of any dimension) is dominated if its link is a simplicial cone. Domination of edges appears to be a very powerful concept, especially when applied to flag complexes. We show that edge collapse (removal of dominated edges) in a flag complex can be performed using only the 1-skeleton of the complex. Furthermore, the residual complex is a flag complex as well. Next we show that, similar to the case of strong collapses, we can use edge collapses to reduce a flag filtration ℱ to a smaller flag filtration ℱ^c with the same persistence. Here again, we only use the 1-skeletons of the complexes. The resulting method to compute ℱ^c is simple and extremely efficient and, when used as a preprocessing for persistence computation, leads to gains of several orders of magnitude w.r.t the state-of-the-art methods (including our previous approach using strong collapse). The method is exact, irrespective of dimension, and improves performance of persistence computation even in low dimensions. This is demonstrated by numerous experiments on publicly available data.
Cite as
Jean-Daniel Boissonnat and Siddharth Pritam. Edge Collapse and Persistence of Flag Complexes. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2020.19,
author = {Boissonnat, Jean-Daniel and Pritam, Siddharth},
title = {{Edge Collapse and Persistence of Flag Complexes}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {19:1--19:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.19},
URN = {urn:nbn:de:0030-drops-121777},
doi = {10.4230/LIPIcs.SoCG.2020.19},
annote = {Keywords: Computational Topology, Topological Data Analysis, Edge Collapse, Simple Collapse, Persistent homology}
}
Document
The Topological Correctness of PL-Approximations of Isomanifolds
Abstract
Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation 𝒯. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.
Cite as
Jean-Daniel Boissonnat and Mathijs Wintraecken. The Topological Correctness of PL-Approximations of Isomanifolds. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2020.20,
author = {Boissonnat, Jean-Daniel and Wintraecken, Mathijs},
title = {{The Topological Correctness of PL-Approximations of Isomanifolds}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {20:1--20:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.20},
URN = {urn:nbn:de:0030-drops-121787},
doi = {10.4230/LIPIcs.SoCG.2020.20},
annote = {Keywords: PL-approximations, isomanifolds, solution manifolds, topological correctness}
}
Document
Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes
Abstract
We study two optimization problems on simplicial complexes with homology over ℤ₂, the minimum bounded chain problem: given a d-dimensional complex 𝒦 embedded in ℝ^(d+1) and a null-homologous (d-1)-cycle C in 𝒦, find the minimum d-chain with boundary C, and the minimum homologous chain problem: given a (d+1)-manifold ℳ and a d-chain D in ℳ, find the minimum d-chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(√{log β_d})-approximation algorithm for the minimum bounded chain problem where β_d is the dth Betti number of 𝒦. Finally, we provide an O(√{log n_{d+1}})-approximation algorithm for the minimum homologous chain problem where n_{d+1} is the number of (d+1)-simplices in ℳ.
Cite as
Glencora Borradaile, William Maxwell, and Amir Nayyeri. Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{borradaile_et_al:LIPIcs.SoCG.2020.21,
author = {Borradaile, Glencora and Maxwell, William and Nayyeri, Amir},
title = {{Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {21:1--21:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.21},
URN = {urn:nbn:de:0030-drops-121799},
doi = {10.4230/LIPIcs.SoCG.2020.21},
annote = {Keywords: computational topology, algorithmic complexity, simplicial complexes}
}
Document
On Rectangle-Decomposable 2-Parameter Persistence Modules
Abstract
This paper addresses two questions: (1) can we identify a sensible class of 2-parameter persistence modules on which the rank invariant is complete? (2) can we determine efficiently whether a given 2-parameter persistence module belongs to this class? We provide positive answers to both questions, and our class of interest is that of rectangle-decomposable modules. Our contributions include: (a) a proof that the rank invariant is complete on rectangle-decomposable modules, together with an inclusion-exclusion formula for counting the multiplicities of the summands; (b) algorithms to check whether a module induced in homology by a bifiltration is rectangle-decomposable, and to decompose it in the affirmative, with a better complexity than state-of-the-art decomposition methods for general 2-parameter persistence modules. Our algorithms are backed up by a new structure theorem, whereby a 2-parameter persistence module is rectangle-decomposable if, and only if, its restrictions to squares are. This local condition is key to the efficiency of our algorithms, and it generalizes previous conditions from the class of block-decomposable modules to the larger one of rectangle-decomposable modules. It also admits an algebraic formulation that turns out to be a weaker version of the one for block-decomposability. Our analysis focuses on the case of modules indexed over finite grids, the more general cases are left as future work.
Cite as
Magnus Bakke Botnan, Vadim Lebovici, and Steve Oudot. On Rectangle-Decomposable 2-Parameter Persistence Modules. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{botnan_et_al:LIPIcs.SoCG.2020.22,
author = {Botnan, Magnus Bakke and Lebovici, Vadim and Oudot, Steve},
title = {{On Rectangle-Decomposable 2-Parameter Persistence Modules}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {22:1--22:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.22},
URN = {urn:nbn:de:0030-drops-121802},
doi = {10.4230/LIPIcs.SoCG.2020.22},
annote = {Keywords: topological data analysis, multiparameter persistence, rank invariant}
}
Document
Robust Anisotropic Power-Functions-Based Filtrations for Clustering
Abstract
We consider robust power-distance functions that approximate the distance function to a compact set, from a noisy sample. We pay particular interest to robust power-distance functions that are anisotropic, in the sense that their sublevel sets are unions of ellipsoids, and not necessarily unions of balls. Using persistence homology on such power-distance functions provides robust clustering schemes. We investigate such clustering schemes and compare the different procedures on synthetic and real datasets. In particular, we enhance the good performance of the anisotropic method for some cases for which classical methods fail.
Cite as
Claire Brécheteau. Robust Anisotropic Power-Functions-Based Filtrations for Clustering. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{brecheteau:LIPIcs.SoCG.2020.23,
author = {Br\'{e}cheteau, Claire},
title = {{Robust Anisotropic Power-Functions-Based Filtrations for Clustering}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {23:1--23:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.23},
URN = {urn:nbn:de:0030-drops-121818},
doi = {10.4230/LIPIcs.SoCG.2020.23},
annote = {Keywords: Power functions, Filtrations, Hierarchical Clustering, Ellipsoids}
}
Document
Geometric Secluded Paths and Planar Satisfiability
Abstract
We consider paths with low exposure to a 2D polygonal domain, i.e., paths which are seen as little as possible; we differentiate between integral exposure (when we care about how long the path sees every point of the domain) and 0/1 exposure (just counting whether a point is seen by the path or not). For the integral exposure, we give a PTAS for finding the minimum-exposure path between two given points in the domain; for the 0/1 version, we prove that in a simple polygon the shortest path has the minimum exposure, while in domains with holes the problem becomes NP-hard. We also highlight connections of the problem to minimum satisfiability and settle hardness of variants of planar min- and max-SAT.
Cite as
Kevin Buchin, Valentin Polishchuk, Leonid Sedov, and Roman Voronov. Geometric Secluded Paths and Planar Satisfiability. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{buchin_et_al:LIPIcs.SoCG.2020.24,
author = {Buchin, Kevin and Polishchuk, Valentin and Sedov, Leonid and Voronov, Roman},
title = {{Geometric Secluded Paths and Planar Satisfiability}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {24:1--24:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.24},
URN = {urn:nbn:de:0030-drops-121827},
doi = {10.4230/LIPIcs.SoCG.2020.24},
annote = {Keywords: Visibility, Route planning, Security/privacy, Planar satisfiability}
}
Document
The Next 350 Million Knots
Abstract
The tabulation of all prime knots up to a given number of crossings was one of the founding problems of knot theory in the 1800s, and continues to be of interest today. Here we extend the tables from 16 to 19 crossings, with a total of 352 152 252 distinct non-trivial prime knots.
The tabulation has two major stages: (1) a combinatorial enumeration stage, which involves generating a provably sufficient set of candidate knot diagrams; and (2) a computational topology stage, which involves identifying and removing duplicate knots, and certifying that all knots that remain are topologically distinct. In this paper we describe the many different algorithmic components in this process, which draw on graph theory, hyperbolic geometry, knot polynomials, normal surface theory, and computational algebra. We also discuss the algorithm engineering challenges in solving difficult topological problems systematically and reliably on hundreds of millions of inputs, despite the fact that no reliably fast algorithms for these problems are known.
Cite as
Benjamin A. Burton. The Next 350 Million Knots. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{burton:LIPIcs.SoCG.2020.25,
author = {Burton, Benjamin A.},
title = {{The Next 350 Million Knots}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {25:1--25:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.25},
URN = {urn:nbn:de:0030-drops-121831},
doi = {10.4230/LIPIcs.SoCG.2020.25},
annote = {Keywords: Computational topology, knots, 3-manifolds, implementation}
}
Document
Elder-Rule-Staircodes for Augmented Metric Spaces
Abstract
An augmented metric space (X, d_X, f_X) is a metric space (X, d_X) equipped with a function f_X: X → ℝ. It arises commonly in practice, e.g, a point cloud X in ℝ^d where each point x∈ X has a density function value f_X(x) associated to it. Such an augmented metric space naturally gives rise to a 2-parameter filtration. However, the resulting 2-parameter persistence module could still be of wild representation type, and may not have simple indecomposables.
In this paper, motivated by the elder-rule for the zeroth homology of a 1-parameter filtration, we propose a barcode-like summary, called the elder-rule-staircode, as a way to encode the zeroth homology of the 2-parameter filtration induced by a finite augmented metric space. Specifically, given a finite (X, d_X, f_X), its elder-rule-staircode consists of n = |X| number of staircase-like blocks in the plane. We show that the fibered barcode, the fibered merge tree, and the graded Betti numbers associated to the zeroth homology of the 2-parameter filtration induced by (X, d_X, f_X) can all be efficiently computed once the elder-rule-staircode is given. Furthermore, for certain special cases, this staircode corresponds exactly to the set of indecomposables of the zeroth homology of the 2-parameter filtration. Finally, we develop and implement an efficient algorithm to compute the elder-rule-staircode in O(n²log n) time, which can be improved to O(n²α(n)) if X is from a fixed dimensional Euclidean space ℝ^d, where α(n) is the inverse Ackermann function.
Cite as
Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang. Elder-Rule-Staircodes for Augmented Metric Spaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{cai_et_al:LIPIcs.SoCG.2020.26,
author = {Cai, Chen and Kim, Woojin and M\'{e}moli, Facundo and Wang, Yusu},
title = {{Elder-Rule-Staircodes for Augmented Metric Spaces}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {26:1--26:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.26},
URN = {urn:nbn:de:0030-drops-121848},
doi = {10.4230/LIPIcs.SoCG.2020.26},
annote = {Keywords: Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers}
}
Document
Faster Approximation Algorithms for Geometric Set Cover
Abstract
We improve the running times of O(1)-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized O(n log⁴n)-time, O(1)-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain a deterministic O(n log³n log log n)-time algorithm. With further new ideas, we obtain a still faster randomized O(n log n(log log n)^O(1))-time algorithm.
For the weighted problem, we also give a randomized O(n log⁴n log log n)-time, O(1)-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.
Cite as
Timothy M. Chan and Qizheng He. Faster Approximation Algorithms for Geometric Set Cover. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{chan_et_al:LIPIcs.SoCG.2020.27,
author = {Chan, Timothy M. and He, Qizheng},
title = {{Faster Approximation Algorithms for Geometric Set Cover}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {27:1--27:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.27},
URN = {urn:nbn:de:0030-drops-121856},
doi = {10.4230/LIPIcs.SoCG.2020.27},
annote = {Keywords: Set cover, approximation algorithms, multiplicate weight update method, random sampling, shallow cuttings}
}
Document
Further Results on Colored Range Searching
Abstract
We present a number of new results about range searching for colored (or "categorical") data:
1) For a set of n colored points in three dimensions, we describe randomized data structures with O(n polylog n) space that can report the distinct colors in any query orthogonal range (axis-aligned box) in O(k polyloglog n) expected time, where k is the number of distinct colors in the range, assuming that coordinates are in {1,…,n}. Previous data structures require O((log n)/(log log n) + k) query time. Our result also implies improvements in higher constant dimensions.
2) Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving O(k log n) expected query time. Previous data structures require O(k log²n) query time.
3) For a set of n colored points in two dimensions, we describe a data structure with O(n polylog n) space that can answer colored "type-2" range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is O((log n)/(log log n) + k log log n), where k is the number of distinct colors in the range. Naively performing k uncolored range counting queries would require O(k (log n)/(log log n)) time.
Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks.
Cite as
Timothy M. Chan, Qizheng He, and Yakov Nekrich. Further Results on Colored Range Searching. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{chan_et_al:LIPIcs.SoCG.2020.28,
author = {Chan, Timothy M. and He, Qizheng and Nekrich, Yakov},
title = {{Further Results on Colored Range Searching}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {28:1--28:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.28},
URN = {urn:nbn:de:0030-drops-121868},
doi = {10.4230/LIPIcs.SoCG.2020.28},
annote = {Keywords: Range searching, geometric data structures, randomized incremental construction, random sampling, word RAM}
}
Document
A Generalization of Self-Improving Algorithms
Abstract
Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances x₁,⋯,x_n follow some unknown product distribution. That is, x_i comes from a fixed unknown distribution 𝒟_i, and the x_i’s are drawn independently. After spending O(n^{1+ε}) time in a learning phase, the subsequent expected running time is O((n+ H)/ε), where H ∈ {H_S,H_DT}, and H_S and H_DT are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the x_i’s under the group product distribution. There is a hidden partition of [1,n] into groups; the x_i’s in the k-th group are fixed unknown functions of the same hidden variable u_k; and the u_k’s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map u_k to x_i’s are well-behaved. After an O(poly(n))-time training phase, we achieve O(n + H_S) and O(nα(n) + H_DT) expected running times for sorting and DT, respectively, where α(⋅) is the inverse Ackermann function.
Cite as
Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong. A Generalization of Self-Improving Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.29,
author = {Cheng, Siu-Wing and Chiu, Man-Kwun and Jin, Kai and Wong, Man Ting},
title = {{A Generalization of Self-Improving Algorithms}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {29:1--29:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.29},
URN = {urn:nbn:de:0030-drops-121873},
doi = {10.4230/LIPIcs.SoCG.2020.29},
annote = {Keywords: expected running time, entropy, sorting, Delaunay triangulation}
}
Document
Dynamic Distribution-Sensitive Point Location
Abstract
We propose a dynamic data structure for the distribution-sensitive point location problem. Suppose that there is a fixed query distribution in ℝ², and we are given an oracle that can return in O(1) time the probability of a query point falling into a polygonal region of constant complexity. We can maintain a convex subdivision S with n vertices such that each query is answered in O(OPT) expected time, where OPT is the minimum expected time of the best linear decision tree for point location in S. The space and construction time are O(n log² n). An update of S as a mixed sequence of k edge insertions and deletions takes O(k log⁵ n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(n log⁵ n) expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.
Cite as
Siu-Wing Cheng and Man-Kit Lau. Dynamic Distribution-Sensitive Point Location. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.30,
author = {Cheng, Siu-Wing and Lau, Man-Kit},
title = {{Dynamic Distribution-Sensitive Point Location}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {30:1--30:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.30},
URN = {urn:nbn:de:0030-drops-121882},
doi = {10.4230/LIPIcs.SoCG.2020.30},
annote = {Keywords: dynamic planar point location, convex subdivision, linear decision tree}
}
Document
No-Dimensional Tverberg Theorems and Algorithms
Abstract
Tverberg’s theorem states that for any k ≥ 2 and any set P ⊂ ℝ^d of at least (d + 1)(k - 1) + 1 points, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem lies in the complexity class PPAD ∩ PLS, but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa [SODA 2019] gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm.
We present a deterministic algorithm that finds for any n-point set P ⊂ ℝ^d and any k ∈ {2, … , n} in O(nd ⌈log k⌉) time a k-partition of P such that there is a ball of radius O((k/√n)diam(P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, and that there are no approximation algorithms that are truly polynomial in any dimension, our result provides a remarkably efficient and simple new notion of approximation.
Our main contribution is to generalize Sarkaria’s method [Israel Journal Math., 1992] to reduce the Tverberg problem to the Colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.
Cite as
Aruni Choudhary and Wolfgang Mulzer. No-Dimensional Tverberg Theorems and Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{choudhary_et_al:LIPIcs.SoCG.2020.31,
author = {Choudhary, Aruni and Mulzer, Wolfgang},
title = {{No-Dimensional Tverberg Theorems and Algorithms}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {31:1--31:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.31},
URN = {urn:nbn:de:0030-drops-121893},
doi = {10.4230/LIPIcs.SoCG.2020.31},
annote = {Keywords: Tverberg’s theorem, Colorful Carath\'{e}odory Theorem, Tensor lifting}
}
Document
Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations
Abstract
This paper considers a particular case of the Optimal Homologous Chain Problem (OHCP) for integer modulo 2 coefficients, where optimality is meant as a minimal lexicographic order on chains induced by a total order on simplices. The matrix reduction algorithm used for persistent homology is used to derive polynomial algorithms solving this problem instance, whereas OHCP is NP-hard in the general case. The complexity is further improved to a quasilinear algorithm by leveraging a dual graph minimum cut formulation when the simplicial complex is a pseudomanifold. We then show how this particular instance of the problem is relevant, by providing an application in the context of point cloud triangulation.
Cite as
David Cohen-Steiner, André Lieutier, and Julien Vuillamy. Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{cohensteiner_et_al:LIPIcs.SoCG.2020.32,
author = {Cohen-Steiner, David and Lieutier, Andr\'{e} and Vuillamy, Julien},
title = {{Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {32:1--32:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.32},
URN = {urn:nbn:de:0030-drops-121908},
doi = {10.4230/LIPIcs.SoCG.2020.32},
annote = {Keywords: OHCP, simplicial homology, triangulation, Delaunay}
}
Document
Finding Closed Quasigeodesics on Convex Polyhedra
Abstract
A closed quasigeodesic is a closed loop on the surface of a polyhedron with at most 180° of surface on both sides at all points; such loops can be locally unfolded straight. In 1949, Pogorelov proved that every convex polyhedron has at least three (non-self-intersecting) closed quasigeodesics, but the proof relies on a nonconstructive topological argument. We present the first finite algorithm to find a closed quasigeodesic on a given convex polyhedron, which is the first positive progress on a 1990 open problem by O'Rourke and Wyman. The algorithm’s running time is pseudopolynomial, namely O(n²/ε² L/𝓁 b) time, where ε is the minimum curvature of a vertex, L is the length of the longest edge, 𝓁 is the smallest distance within a face between a vertex and a nonincident edge (minimum feature size of any face), and b is the maximum number of bits of an integer in a constant-size radical expression of a real number representing the polyhedron. We take special care in the model of computation and needed precision, showing that we can achieve the stated running time on a pointer machine supporting constant-time w-bit arithmetic operations where w = Ω(lg b).
Cite as
Erik D. Demaine, Adam C. Hesterberg, and Jason S. Ku. Finding Closed Quasigeodesics on Convex Polyhedra. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{demaine_et_al:LIPIcs.SoCG.2020.33,
author = {Demaine, Erik D. and Hesterberg, Adam C. and Ku, Jason S.},
title = {{Finding Closed Quasigeodesics on Convex Polyhedra}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {33:1--33:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.33},
URN = {urn:nbn:de:0030-drops-121912},
doi = {10.4230/LIPIcs.SoCG.2020.33},
annote = {Keywords: polyhedra, geodesic, pseudopolynomial, geometric precision}
}
Document
The Stretch Factor of Hexagon-Delaunay Triangulations
Abstract
The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch factor) of a Delaunay triangulation is one of the longstanding open problems in computational geometry. Over the years, a series of upper and lower bounds on the exact stretch factor have been obtained but the gap between them is still large. An alternative approach to solving the problem is to develop techniques for computing the exact stretch factor of "easier" types of Delaunay triangulations, in particular those defined using regular-polygons instead of a circle. Tight bounds exist for Delaunay triangulations defined using an equilateral triangle and a square. In this paper, we determine the exact stretch factor of Delaunay triangulations defined using a regular hexagon: It is 2. We think that the main contribution of this paper are the two techniques we have developed to compute tight upper bounds for the stretch factor of Hexagon-Delaunay triangulations.
Cite as
Michael Dennis, Ljubomir Perković, and Duru Türkoğlu. The Stretch Factor of Hexagon-Delaunay Triangulations. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{dennis_et_al:LIPIcs.SoCG.2020.34,
author = {Dennis, Michael and Perkovi\'{c}, Ljubomir and T\"{u}rko\u{g}lu, Duru},
title = {{The Stretch Factor of Hexagon-Delaunay Triangulations}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {34:1--34:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.34},
URN = {urn:nbn:de:0030-drops-121920},
doi = {10.4230/LIPIcs.SoCG.2020.34},
annote = {Keywords: Delaunay triangulation, geometric spanner, plane spanner, stretch factor, spanning ratio}
}
Document
Flipping Geometric Triangulations on Hyperbolic Surfaces
Abstract
We consider geometric triangulations of surfaces, i.e., triangulations whose edges can be realized by disjoint geodesic segments. We prove that the flip graph of geometric triangulations with fixed vertices of a flat torus or a closed hyperbolic surface is connected. We give upper bounds on the number of edge flips that are necessary to transform any geometric triangulation on such a surface into a Delaunay triangulation.
Cite as
Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud. Flipping Geometric Triangulations on Hyperbolic Surfaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{despre_et_al:LIPIcs.SoCG.2020.35,
author = {Despr\'{e}, Vincent and Schlenker, Jean-Marc and Teillaud, Monique},
title = {{Flipping Geometric Triangulations on Hyperbolic Surfaces}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {35:1--35:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.35},
URN = {urn:nbn:de:0030-drops-121939},
doi = {10.4230/LIPIcs.SoCG.2020.35},
annote = {Keywords: Hyperbolic surface, Topology, Delaunay triangulation, Algorithm, Flip graph}
}
Document
An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology
Abstract
This paper focuses on developing an efficient algorithm for analyzing a directed network (graph) from a topological viewpoint. A prevalent technique for such topological analysis involves computation of homology groups and their persistence. These concepts are well suited for spaces that are not directed. As a result, one needs a concept of homology that accommodates orientations in input space. Path-homology developed for directed graphs by Grigoryan, Lin, Muranov and Yau has been effectively adapted for this purpose recently by Chowdhury and Mémoli. They also give an algorithm to compute this path-homology. Our main contribution in this paper is an algorithm that computes this path-homology and its persistence more efficiently for the 1-dimensional (H₁) case. In developing such an algorithm, we discover various structures and their efficient computations that aid computing the 1-dimensional path-homology. We implement our algorithm and present some preliminary experimental results.
Cite as
Tamal K. Dey, Tianqi Li, and Yusu Wang. An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{dey_et_al:LIPIcs.SoCG.2020.36,
author = {Dey, Tamal K. and Li, Tianqi and Wang, Yusu},
title = {{An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {36:1--36:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.36},
URN = {urn:nbn:de:0030-drops-121944},
doi = {10.4230/LIPIcs.SoCG.2020.36},
annote = {Keywords: computational topology, directed graph, path homology, persistent path homology}
}
Document
Persistence of the Conley Index in Combinatorial Dynamical Systems
Abstract
A combinatorial framework for dynamical systems provides an avenue for connecting classical dynamics with data-oriented, algorithmic methods. Combinatorial vector fields introduced by Forman [R. Forman, 1998; R. Forman, 1998] and their recent generalization to multivector fields [Mrozek, 2017] have provided a starting point for building such a connection. In this work, we strengthen this relationship by placing the Conley index in the persistent homology setting. Conley indices are homological features associated with so-called isolated invariant sets, so a change in the Conley index is a response to perturbation in an underlying multivector field. We show how one can use zigzag persistence to summarize changes to the Conley index, and we develop techniques to capture such changes in the presence of noise. We conclude by developing an algorithm to "track" features in a changing multivector field.
Cite as
Tamal K. Dey, Marian Mrozek, and Ryan Slechta. Persistence of the Conley Index in Combinatorial Dynamical Systems. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{dey_et_al:LIPIcs.SoCG.2020.37,
author = {Dey, Tamal K. and Mrozek, Marian and Slechta, Ryan},
title = {{Persistence of the Conley Index in Combinatorial Dynamical Systems}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {37:1--37:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.37},
URN = {urn:nbn:de:0030-drops-121958},
doi = {10.4230/LIPIcs.SoCG.2020.37},
annote = {Keywords: Dynamical systems, combinatorial vector field, multivector, Conley index, persistence}
}
Document
On Implementing Straight Skeletons: Challenges and Experiences
Abstract
We present Cgal implementations of two algorithms for computing straight skeletons in the plane, based on exact arithmetic. One code, named Surfer2, can handle multiplicatively weighted planar straight-line graphs (PSLGs) while our second code, Monos, is specifically targeted at monotone polygons. Both codes are available on GitHub. We discuss algorithmic as well as implementational and engineering details of both codes. Furthermore, we present the results of an extensive performance evaluation in which we compared Surfer2 and Monos to the straight-skeleton package included in Cgal. It is not surprising that our special-purpose code Monos outperforms Cgal’s straight-skeleton implementation. But our tests provide ample evidence that also Surfer2 can be expected to be faster and to consume significantly less memory than the Cgal code. And, of course, Surfer2 is more versatile because it can handle multiplicative weights and general PSLGs as input. Thus, Surfer2 currently is the fastest and most general straight-skeleton code available.
Cite as
Günther Eder, Martin Held, and Peter Palfrader. On Implementing Straight Skeletons: Challenges and Experiences. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{eder_et_al:LIPIcs.SoCG.2020.38,
author = {Eder, G\"{u}nther and Held, Martin and Palfrader, Peter},
title = {{On Implementing Straight Skeletons: Challenges and Experiences}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {38:1--38:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.38},
URN = {urn:nbn:de:0030-drops-121964},
doi = {10.4230/LIPIcs.SoCG.2020.38},
annote = {Keywords: weighted straight skeleton, implementation, algorithm engineering, experiments, Cgal, Core}
}
Document
Removing Connected Obstacles in the Plane Is FPT
Abstract
Given two points in the plane, a set of obstacles defined by closed curves, and an integer k, does there exist a path between the two designated points intersecting at most k of the obstacles? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory, wireless computing, and motion planning. It remains NP-hard even when the obstacles are very simple geometric shapes (e.g., unit-length line segments). In this paper, we show that the problem is fixed-parameter tractable (FPT) parameterized by k, by giving an algorithm with running time k^O(k³) n^O(1). Here n is the number connected areas in the plane drawing of all the obstacles.
Cite as
Eduard Eiben and Daniel Lokshtanov. Removing Connected Obstacles in the Plane Is FPT. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{eiben_et_al:LIPIcs.SoCG.2020.39,
author = {Eiben, Eduard and Lokshtanov, Daniel},
title = {{Removing Connected Obstacles in the Plane Is FPT}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {39:1--39:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.39},
URN = {urn:nbn:de:0030-drops-121972},
doi = {10.4230/LIPIcs.SoCG.2020.39},
annote = {Keywords: parameterized complexity and algorithms, planar graphs, motion planning, barrier coverage, barrier resilience, colored path, minimum constraint removal}
}
Document
A Toroidal Maxwell-Cremona-Delaunay Correspondence
Abstract
We consider three classes of geodesic embeddings of graphs on Euclidean flat tori:
- A torus graph G is equilibrium if it is possible to place positive weights on the edges, such that the weighted edge vectors incident to each vertex of G sum to zero.
- A torus graph G is reciprocal if there is a geodesic embedding of the dual graph G^* on the same flat torus, where each edge of G is orthogonal to the corresponding dual edge in G^*.
- A torus graph G is coherent if it is possible to assign weights to the vertices, so that G is the (intrinsic) weighted Delaunay graph of its vertices. The classical Maxwell-Cremona correspondence and the well-known correspondence between convex hulls and weighted Delaunay triangulations imply that the analogous concepts for plane graphs (with convex outer faces) are equivalent. Indeed, all three conditions are equivalent to G being the projection of the 1-skeleton of the lower convex hull of points in ℝ³. However, this three-way equivalence does not extend directly to geodesic graphs on flat tori. On any flat torus, reciprocal and coherent graphs are equivalent, and every reciprocal graph is equilibrium, but not every equilibrium graph is reciprocal. We establish a weaker correspondence: Every equilibrium graph on any flat torus is affinely equivalent to a reciprocal/coherent graph on some flat torus.
Cite as
Jeff Erickson and Patrick Lin. A Toroidal Maxwell-Cremona-Delaunay Correspondence. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{erickson_et_al:LIPIcs.SoCG.2020.40,
author = {Erickson, Jeff and Lin, Patrick},
title = {{A Toroidal Maxwell-Cremona-Delaunay Correspondence}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {40:1--40:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.40},
URN = {urn:nbn:de:0030-drops-121984},
doi = {10.4230/LIPIcs.SoCG.2020.40},
annote = {Keywords: combinatorial topology, geometric graphs, homology, flat torus, spring embedding, intrinsic Delaunay}
}
Document
Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries
Abstract
We study the interplay between the recently-defined concept of minimum homotopy area and the classical topic of self-overlapping curves. The latter are plane curves that are the image of the boundary of an immersed disk. Our first contribution is to prove new sufficient combinatorial conditions for a curve to be self-overlapping. We show that a curve γ with Whitney index 1 and without any self-overlapping subcurves is self-overlapping. As a corollary, we obtain sufficient conditions for self-overlapping ness solely in terms of the Whitney index of the curve and its subcurves. These results follow from our second contribution, which shows that any plane curve γ, modulo a basepoint condition, is transformed into an interior boundary by wrapping around γ with Jordan curves. In fact, we show that n+1 wraps suffice, where γ has n vertices. Our third contribution is to prove the equivalence of various definitions of self-overlapping curves and interior boundaries, often implicit in the literature. We also introduce and characterize zero-obstinance curves, a further generalization of interior boundaries defined by optimality in minimum homotopy area.
Cite as
Parker Evans, Brittany Terese Fasy, and Carola Wenk. Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{evans_et_al:LIPIcs.SoCG.2020.41,
author = {Evans, Parker and Fasy, Brittany Terese and Wenk, Carola},
title = {{Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {41:1--41:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.41},
URN = {urn:nbn:de:0030-drops-121993},
doi = {10.4230/LIPIcs.SoCG.2020.41},
annote = {Keywords: Self-overlapping curves, interior boundaries, minimum homotopy area, immersion}
}
Document
Worst-Case Optimal Covering of Rectangles by Disks
Abstract
We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any λ ≥ 1, the critical covering area A^*(λ) is the minimum value for which any set of disks with total area at least A^*(λ) can cover a rectangle of dimensions λ× 1. We show that there is a threshold value λ₂ = √{√7/2 - 1/4} ≈ 1.035797…, such that for λ < λ₂ the critical covering area A^*(λ) is A^*(λ) = 3π(λ²/16 + 5/32 + 9/(256λ²)), and for λ ≥ λ₂, the critical area is A^*(λ)=π(λ²+2)/4; these values are tight. For the special case λ=1, i.e., for covering a unit square, the critical covering area is 195π/256 ≈ 2.39301…. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.
Cite as
Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich, Christian Scheffer, and Sahil Shah. Worst-Case Optimal Covering of Rectangles by Disks. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{fekete_et_al:LIPIcs.SoCG.2020.42,
author = {Fekete, S\'{a}ndor P. and Gupta, Utkarsh and Keldenich, Phillip and Scheffer, Christian and Shah, Sahil},
title = {{Worst-Case Optimal Covering of Rectangles by Disks}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {42:1--42:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.42},
URN = {urn:nbn:de:0030-drops-122003},
doi = {10.4230/LIPIcs.SoCG.2020.42},
annote = {Keywords: Disk covering, critical density, covering coefficient, tight worst-case bound, interval arithmetic, approximation}
}
Document
Minimum Scan Cover with Angular Transition Costs
Abstract
We provide a comprehensive study of a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs (msc), we are given a graph G that is embedded in Euclidean space. The edges of G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan.
We show that msc is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in Θ(log χ(G)), while for 3D the minimum scan time is not upper bounded by χ(G). We use this relationship to prove that the existence of a constant-factor approximation implies P=NP, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of 3/2, even for bipartite graphs; conversely, we present a 9/2-approximation algorithm for this scenario. Generally, we give an O(c)-approximation for k-colored graphs with k ≤ χ(G)^c. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.
Cite as
Sándor P. Fekete, Linda Kleist, and Dominik Krupke. Minimum Scan Cover with Angular Transition Costs. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{fekete_et_al:LIPIcs.SoCG.2020.43,
author = {Fekete, S\'{a}ndor P. and Kleist, Linda and Krupke, Dominik},
title = {{Minimum Scan Cover with Angular Transition Costs}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {43:1--43:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.43},
URN = {urn:nbn:de:0030-drops-122014},
doi = {10.4230/LIPIcs.SoCG.2020.43},
annote = {Keywords: Graph scanning, graph coloring, angular metric, complexity, approximation, scheduling}
}
Document
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
Abstract
We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2^{𝒪(√k)}(n+m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs cannot be solved in time 2^{o(√k)}(n+m)^𝒪(1) [de Berg et al., STOC 2018], hence our algorithm is optimal. Besides the 2^{𝒪(√k)}(n+m)^𝒪(1)-time algorithm for the (arguably) much simpler Vertex Cover problem by de Berg et al. [STOC 2018] (which easily follows from the existence of a 2k-vertex kernel for the problem), this is the only known ETH-optimal fixed-parameter tractable algorithm on UDGs. Previously, Long Path and Long Cycle on unit disk graphs were only known to be solvable in time 2^{𝒪(√klog k)}(n+m). This algorithm involved the introduction of a new type of a tree decomposition, entailing the design of a very tedious dynamic programming procedure. Our algorithm is substantially simpler: we completely avoid the use of this new type of tree decomposition. Instead, we use a marking procedure to reduce the problem to (a weighted version of) itself on a standard tree decomposition of width 𝒪(√k).
Cite as
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{fomin_et_al:LIPIcs.SoCG.2020.44,
author = {Fomin, Fedor V. and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav},
title = {{ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {44:1--44:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.44},
URN = {urn:nbn:de:0030-drops-122024},
doi = {10.4230/LIPIcs.SoCG.2020.44},
annote = {Keywords: Optimality Program, ETH, Unit Disk Graphs, Parameterized Complexity, Long Path, Long Cycle}
}
Document
A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread
Abstract
The geometric transportation problem takes as input a set of points P in d-dimensional Euclidean space and a supply function μ : P → ℝ. The goal is to find a transportation map, a non-negative assignment τ : P × P → ℝ_{≥ 0} to pairs of points, so the total assignment leaving each point is equal to its supply, i.e., ∑_{r ∈ P} τ(q, r) - ∑_{p ∈ P} τ(p, q) = μ(q) for all points q ∈ P. The goal is to minimize the weighted sum of Euclidean distances for the pairs, ∑_{(p, q) ∈ P × P} τ(p, q) ⋅ ||q - p||₂.
We describe the first algorithm for this problem that returns, with high probability, a (1 + ε)-approximation to the optimal transportation map in O(n poly(1 / ε) polylog n) time. In contrast to the previous best algorithms for this problem, our near-linear running time bound is independent of the spread of P and the magnitude of its real-valued supplies.
Cite as
Kyle Fox and Jiashuai Lu. A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{fox_et_al:LIPIcs.SoCG.2020.45,
author = {Fox, Kyle and Lu, Jiashuai},
title = {{A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {45:1--45:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.45},
URN = {urn:nbn:de:0030-drops-122034},
doi = {10.4230/LIPIcs.SoCG.2020.45},
annote = {Keywords: Transportation map, earth mover’s distance, shape matching, approximation algorithms}
}
Document
Bounded VC-Dimension Implies the Schur-Erdős Conjecture
Abstract
In 1916, Schur introduced the Ramsey number r(3;m), which is the minimum integer n > 1 such that for any m-coloring of the edges of the complete graph K_n, there is a monochromatic copy of K₃. He showed that r(3;m) ≤ O(m!), and a simple construction demonstrates that r(3;m) ≥ 2^Ω(m). An old conjecture of Erdős states that r(3;m) = 2^Θ(m). In this note, we prove the conjecture for m-colorings with bounded VC-dimension, that is, for m-colorings with the property that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-dimension.
Cite as
Jacob Fox, János Pach, and Andrew Suk. Bounded VC-Dimension Implies the Schur-Erdős Conjecture. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 46:1-46:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{fox_et_al:LIPIcs.SoCG.2020.46,
author = {Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
title = {{Bounded VC-Dimension Implies the Schur-Erd\H{o}s Conjecture}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {46:1--46:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.46},
URN = {urn:nbn:de:0030-drops-122046},
doi = {10.4230/LIPIcs.SoCG.2020.46},
annote = {Keywords: Ramsey theory, VC-dimension, Multicolor Ramsey numbers}
}
Document
Almost-Monochromatic Sets and the Chromatic Number of the Plane
Abstract
In a colouring of ℝ^d a pair (S,s₀) with S ⊆ ℝ^d and with s₀ ∈ S is almost-monochromatic if S⧵{s₀} is monochromatic but S is not. We consider questions about finding almost-monochromatic similar copies of pairs (S,s₀) in colourings of ℝ^d, ℤ^d, and of ℚ under some restrictions on the colouring.
Among other results, we characterise those (S,s₀) with S ⊆ ℤ for which every finite colouring of ℝ without an infinite monochromatic arithmetic progression contains an almost-monochromatic similar copy of (S,s₀). We also show that if S ⊆ ℤ^d and s₀ is outside of the convex hull of S⧵{s₀}, then every finite colouring of ℝ^d without a monochromatic similar copy of ℤ^d contains an almost-monochromatic similar copy of (S,s₀). Further, we propose an approach based on finding almost-monochromatic sets that might lead to a human-verifiable proof of χ(ℝ²) ≥ 5.
Cite as
Nóra Frankl, Tamás Hubai, and Dömötör Pálvölgyi. Almost-Monochromatic Sets and the Chromatic Number of the Plane. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{frankl_et_al:LIPIcs.SoCG.2020.47,
author = {Frankl, N\'{o}ra and Hubai, Tam\'{a}s and P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r},
title = {{Almost-Monochromatic Sets and the Chromatic Number of the Plane}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {47:1--47:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.47},
URN = {urn:nbn:de:0030-drops-122054},
doi = {10.4230/LIPIcs.SoCG.2020.47},
annote = {Keywords: discrete geometry, Hadwiger-Nelson problem, Euclidean Ramsey theory}
}
Document
Almost Sharp Bounds on the Number of Discrete Chains in the Plane
Abstract
The following generalisation of the Erdős unit distance problem was recently suggested by Palsson, Senger and Sheffer. For a sequence δ=(δ₁,… ,δ_k) of k distances, a (k+1)-tuple (p₁,… ,p_{k+1}) of distinct points in ℝ^d is called a (k,δ)-chain if ‖p_j-p_{j+1}‖ = δ_j for every 1 ≤ j ≤ k. What is the maximum number C_k^d(n) of (k,δ)-chains in a set of n points in ℝ^d, where the maximum is taken over all δ? Improving the results of Palsson, Senger and Sheffer, we essentially determine this maximum for all k in the planar case. It is only for k ≡ 1 (mod 3) that the answer depends on the maximum number of unit distances in a set of n points. We also obtain almost sharp results for even k in dimension 3.
Cite as
Nóra Frankl and Andrey Kupavskii. Almost Sharp Bounds on the Number of Discrete Chains in the Plane. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{frankl_et_al:LIPIcs.SoCG.2020.48,
author = {Frankl, N\'{o}ra and Kupavskii, Andrey},
title = {{Almost Sharp Bounds on the Number of Discrete Chains in the Plane}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {48:1--48:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.48},
URN = {urn:nbn:de:0030-drops-122064},
doi = {10.4230/LIPIcs.SoCG.2020.48},
annote = {Keywords: unit distance problem, unit distance graphs, discrete chains}
}
Document
Convex Hulls of Random Order Types
Abstract
We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented matroids of rank 3):
(a) The number of extreme points in an n-point order type, chosen uniformly at random from all such order types, is on average 4+o(1). For labeled order types, this number has average 4-8/(n^2 - n +2) and variance at most 3.
(b) The (labeled) order types read off a set of n points sampled independently from the uniform measure on a convex planar domain, smooth or polygonal, or from a Gaussian distribution are concentrated, i.e., such sampling typically encounters only a vanishingly small fraction of all order types of the given size. Result (a) generalizes to arbitrary dimension d for labeled order types with the average number of extreme points 2d+o(1) and constant variance. We also discuss to what extent our methods generalize to the abstract setting of uniform acyclic oriented matroids. Moreover, our methods allow to show the following relative of the Erdős-Szekeres theorem: for any fixed k, as n → ∞, a proportion 1 - O(1/n) of the n-point simple order types contain a triangle enclosing a convex k-chain over an edge.
For the unlabeled case in (a), we prove that for any antipodal, finite subset of the 2-dimensional sphere, the group of orientation preserving bijections is cyclic, dihedral or one of A₄, S₄ or A₅ (and each case is possible). These are the finite subgroups of SO(3) and our proof follows the lines of their characterization by Felix Klein.
Cite as
Xavier Goaoc and Emo Welzl. Convex Hulls of Random Order Types. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{goaoc_et_al:LIPIcs.SoCG.2020.49,
author = {Goaoc, Xavier and Welzl, Emo},
title = {{Convex Hulls of Random Order Types}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {49:1--49:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.49},
URN = {urn:nbn:de:0030-drops-122074},
doi = {10.4230/LIPIcs.SoCG.2020.49},
annote = {Keywords: order type, oriented matroid, Sylvester’s Four-Point Problem, random convex hull, projective plane, excluded pattern, Hadwiger’s transversal theorem, hairy ball theorem}
}
Document
Fast Algorithms for Geometric Consensuses
Abstract
Let P be a set of n points in ℝ^d in general position. A median hyperplane (roughly) splits the point set P in half. The yolk of P is the ball of smallest radius intersecting all median hyperplanes of P. The egg of P is the ball of smallest radius intersecting all hyperplanes which contain exactly d points of P.
We present exact algorithms for computing the yolk and the egg of a point set, both running in expected time O(n^(d-1) log n). The running time of the new algorithm is a polynomial time improvement over existing algorithms. We also present algorithms for several related problems, such as computing the Tukey and center balls of a point set, among others.
Cite as
Sariel Har-Peled and Mitchell Jones. Fast Algorithms for Geometric Consensuses. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{harpeled_et_al:LIPIcs.SoCG.2020.50,
author = {Har-Peled, Sariel and Jones, Mitchell},
title = {{Fast Algorithms for Geometric Consensuses}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {50:1--50:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.50},
URN = {urn:nbn:de:0030-drops-122088},
doi = {10.4230/LIPIcs.SoCG.2020.50},
annote = {Keywords: Geometric optimization, centerpoint, voting games}
}
Document
Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles
Abstract
Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect.
We present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in d dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant d and ε>0, assuming that the coordinates of all input objects are in [0, N]^d and each of their edges has length at least 1. We obtain the following results:
- For weighted intervals, we maintain a (1+ε)-approximate solution.
- For d-dimensional hypercubes we maintain a (1+ε)2^d-approximate solution in the unweighted case and a O(2^d)-approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1+ε)-approximate solution one needs polynomial update time for d ≥ 2 if the ETH holds.
- For weighted d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1+ε)log^{d-1}N.
Cite as
Monika Henzinger, Stefan Neumann, and Andreas Wiese. Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{henzinger_et_al:LIPIcs.SoCG.2020.51,
author = {Henzinger, Monika and Neumann, Stefan and Wiese, Andreas},
title = {{Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {51:1--51:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.51},
URN = {urn:nbn:de:0030-drops-122094},
doi = {10.4230/LIPIcs.SoCG.2020.51},
annote = {Keywords: Dynamic algorithms, independent set, approximation algorithms, interval graphs, geometric intersection graphs}
}
Document
How to Find a Point in the Convex Hull Privately
Abstract
We study the question of how to compute a point in the convex hull of an input set S of n points in ℝ^d in a differentially private manner. This question, which is trivial without privacy requirements, turns out to be quite deep when imposing differential privacy. In particular, it is known that the input points must reside on a fixed finite subset G ⊆ ℝ^d, and furthermore, the size of S must grow with the size of G. Previous works [Amos Beimel et al., 2010; Amos Beimel et al., 2019; Amos Beimel et al., 2013; Mark Bun et al., 2018; Mark Bun et al., 2015; Haim Kaplan et al., 2019] focused on understanding how n needs to grow with |G|, and showed that n=O(d^2.5 ⋅ 8^(log^*|G|)) suffices (so n does not have to grow significantly with |G|). However, the available constructions exhibit running time at least |G|^d², where typically |G|=X^d for some (large) discretization parameter X, so the running time is in fact Ω(X^d³).
In this paper we give a differentially private algorithm that runs in O(n^d) time, assuming that n=Ω(d⁴ log X). To get this result we study and exploit some structural properties of the Tukey levels (the regions D_{≥ k} consisting of points whose Tukey depth is at least k, for k=0,1,…). In particular, we derive lower bounds on their volumes for point sets S in general position, and develop a rather subtle mechanism for handling point sets S in degenerate position (where the deep Tukey regions have zero volume). A naive approach to the construction of the Tukey regions requires n^O(d²) time. To reduce the cost to O(n^d), we use an approximation scheme for estimating the volumes of the Tukey regions (within their affine spans in case of degeneracy), and for sampling a point from such a region, a scheme that is based on the volume estimation framework of Lovász and Vempala [László Lovász and Santosh S. Vempala, 2006] and of Cousins and Vempala [Ben Cousins and Santosh S. Vempala, 2018]. Making this framework differentially private raises a set of technical challenges that we address.
Cite as
Haim Kaplan, Micha Sharir, and Uri Stemmer. How to Find a Point in the Convex Hull Privately. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kaplan_et_al:LIPIcs.SoCG.2020.52,
author = {Kaplan, Haim and Sharir, Micha and Stemmer, Uri},
title = {{How to Find a Point in the Convex Hull Privately}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {52:1--52:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.52},
URN = {urn:nbn:de:0030-drops-122107},
doi = {10.4230/LIPIcs.SoCG.2020.52},
annote = {Keywords: Differential privacy, Tukey depth, Convex hull}
}
Document
Efficient Approximation of the Matching Distance for 2-Parameter Persistence
Abstract
In topological data analysis, the matching distance is a computationally tractable metric on multi-filtered simplicial complexes. We design efficient algorithms for approximating the matching distance of two bi-filtered complexes to any desired precision ε>0. Our approach is based on a quad-tree refinement strategy introduced by Biasotti et al., but we recast their approach entirely in geometric terms. This point of view leads to several novel observations resulting in a practically faster algorithm. We demonstrate this speed-up by experimental comparison and provide our code in a public repository which provides the first efficient publicly available implementation of the matching distance.
Cite as
Michael Kerber and Arnur Nigmetov. Efficient Approximation of the Matching Distance for 2-Parameter Persistence. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kerber_et_al:LIPIcs.SoCG.2020.53,
author = {Kerber, Michael and Nigmetov, Arnur},
title = {{Efficient Approximation of the Matching Distance for 2-Parameter Persistence}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {53:1--53:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.53},
URN = {urn:nbn:de:0030-drops-122116},
doi = {10.4230/LIPIcs.SoCG.2020.53},
annote = {Keywords: multi-parameter persistence, matching distance, approximation algorithm}
}
Document
Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex
Abstract
We derive conditions under which the reconstruction of a target space is topologically correct via the Čech complex or the Vietoris-Rips complex obtained from possibly noisy point cloud data. We provide two novel theoretical results. First, we describe sufficient conditions under which any non-empty intersection of finitely many Euclidean balls intersected with a positive reach set is contractible, so that the Nerve theorem applies for the restricted Čech complex. Second, we demonstrate the homotopy equivalence of a positive μ-reach set and its offsets. Applying these results to the restricted Čech complex and using the interleaving relations with the Čech complex (or the Vietoris-Rips complex), we formulate conditions guaranteeing that the target space is homotopy equivalent to the Čech complex (or the Vietoris-Rips complex), in terms of the μ-reach. Our results sharpen existing results.
Cite as
Jisu Kim, Jaehyeok Shin, Frédéric Chazal, Alessandro Rinaldo, and Larry Wasserman. Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kim_et_al:LIPIcs.SoCG.2020.54,
author = {Kim, Jisu and Shin, Jaehyeok and Chazal, Fr\'{e}d\'{e}ric and Rinaldo, Alessandro and Wasserman, Larry},
title = {{Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {54:1--54:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.54},
URN = {urn:nbn:de:0030-drops-122129},
doi = {10.4230/LIPIcs.SoCG.2020.54},
annote = {Keywords: Computational topology, Homotopy reconstruction, Homotopy Equivalence, Vietoris-Rips complex, \v{C}ech complex, Reach, \mu-reach, Nerve Theorem, Offset, Double offset, Consistency}
}
Document
A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP
Abstract
We study the traveling salesman problem in the hyperbolic plane of Gaussian curvature -1. Let α denote the minimum distance between any two input points. Using a new separator theorem and a new rerouting argument, we give an n^{O(log² n)max(1,1/α)} algorithm for Hyperbolic TSP. This is quasi-polynomial time if α is at least some absolute constant, and it grows to n^O(√n) as α decreases to log² n/√n. (For even smaller values of α, we can use a planarity-based algorithm of Hwang et al. (1993), which gives a running time of n^O(√n).)
Cite as
Sándor Kisfaludi-Bak. A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kisfaludibak:LIPIcs.SoCG.2020.55,
author = {Kisfaludi-Bak, S\'{a}ndor},
title = {{A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {55:1--55:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.55},
URN = {urn:nbn:de:0030-drops-122135},
doi = {10.4230/LIPIcs.SoCG.2020.55},
annote = {Keywords: Computational geometry, Hyperbolic geometry, Traveling salesman}
}
Document
Intrinsic Topological Transforms via the Distance Kernel Embedding
Abstract
Topological transforms are parametrized families of topological invariants, which, by analogy with transforms in signal processing, are much more discriminative than single measurements. The first two topological transforms to be defined were the Persistent Homology Transform (PHT) and Euler Characteristic Transform (ECT), both of which apply to shapes embedded in Euclidean space. The contribution of this paper is to define topological transforms for abstract metric measure spaces. Our proposed pipeline is to pre-compose the PHT or ECT with a Euclidean embedding derived from the eigenfunctions and eigenvalues of an integral operator. To that end, we define and study an integral operator called the distance kernel operator, and demonstrate that it gives rise to stable and quasi-injective topological transforms. We conclude with some numerical experiments, wherein we compute and compare the eigenfunctions and eigenvalues of our operator across a range of standard 2- and 3-manifolds.
Cite as
Clément Maria, Steve Oudot, and Elchanan Solomon. Intrinsic Topological Transforms via the Distance Kernel Embedding. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{maria_et_al:LIPIcs.SoCG.2020.56,
author = {Maria, Cl\'{e}ment and Oudot, Steve and Solomon, Elchanan},
title = {{Intrinsic Topological Transforms via the Distance Kernel Embedding}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {56:1--56:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.56},
URN = {urn:nbn:de:0030-drops-122145},
doi = {10.4230/LIPIcs.SoCG.2020.56},
annote = {Keywords: Topological Transforms, Persistent Homology, Inverse Problems, Spectral Geometry, Algebraic Topology, Topological Data Analysis}
}
Document
Long Alternating Paths Exist
Abstract
Let P be a set of 2n points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on P of length 𝓁 is a sequence p₁, … , p_𝓁 of 𝓁 points from P so that (i) all points are pairwise distinct; (ii) any two consecutive points p_i, p_{i+1} have different colors; and (iii) any two segments p_i p_{i+1} and p_j p_{j+1} have disjoint relative interiors, for i ≠ j.
We show that there is an absolute constant ε > 0, independent of n and of the coloring, such that P always admits a non-crossing alternating path of length at least (1 + ε)n. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least (1 + ε)n points of P. This is a properly colored matching whose segments are pairwise disjoint and intersected by common line. For both versions, this is the first improvement of the easily obtained lower bound of n by an additive term linear in n. The best known published upper bounds are asymptotically of order 4n/3+o(n).
Cite as
Wolfgang Mulzer and Pavel Valtr. Long Alternating Paths Exist. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{mulzer_et_al:LIPIcs.SoCG.2020.57,
author = {Mulzer, Wolfgang and Valtr, Pavel},
title = {{Long Alternating Paths Exist}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {57:1--57:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.57},
URN = {urn:nbn:de:0030-drops-122152},
doi = {10.4230/LIPIcs.SoCG.2020.57},
annote = {Keywords: Non-crossing path, bichromatic point sets}
}
Document
k-Median Clustering Under Discrete Fréchet and Hausdorff Distances
Abstract
We give the first near-linear time (1+ε)-approximation algorithm for k-median clustering of polygonal trajectories under the discrete Fréchet distance, and the first polynomial time (1+ε)-approximation algorithm for k-median clustering of finite point sets under the Hausdorff distance, provided the cluster centers, ambient dimension, and k are bounded by a constant. The main technique is a general framework for solving clustering problems where the cluster centers are restricted to come from a simpler metric space. We precisely characterize conditions on the simpler metric space of the cluster centers that allow faster (1+ε)-approximations for the k-median problem. We also show that the k-median problem under Hausdorff distance is NP-Hard.
Cite as
Abhinandan Nath and Erin Taylor. k-Median Clustering Under Discrete Fréchet and Hausdorff Distances. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{nath_et_al:LIPIcs.SoCG.2020.58,
author = {Nath, Abhinandan and Taylor, Erin},
title = {{k-Median Clustering Under Discrete Fr\'{e}chet and Hausdorff Distances}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {58:1--58:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.58},
URN = {urn:nbn:de:0030-drops-122161},
doi = {10.4230/LIPIcs.SoCG.2020.58},
annote = {Keywords: Clustering, k-median, trajectories, point sets, discrete Fr\'{e}chet distance, Hausdorff distance}
}
Document
Four-Dimensional Dominance Range Reporting in Linear Space
Abstract
In this paper we study the four-dimensional dominance range reporting problem and present data structures with linear or almost-linear space usage. Our results can be also used to answer four-dimensional queries that are bounded on five sides. The first data structure presented in this paper uses linear space and answers queries in O(log^{1+ε} n + k log^ε n) time, where k is the number of reported points, n is the number of points in the data structure, and ε is an arbitrarily small positive constant. Our second data structure uses O(n log^ε n) space and answers queries in O(log n+k) time.
These are the first data structures for this problem that use linear (resp. O(n log^ε n)) space and answer queries in poly-logarithmic time. For comparison the fastest previously known linear-space or O(n log^ε n)-space data structure supports queries in O(n^ε + k) time (Bentley and Mauer, 1980). Our results can be generalized to d ≥ 4 dimensions. For example, we can answer d-dimensional dominance range reporting queries in O(log log n (log n/log log n)^{d-3} + k) time using O(n log^{d-4+ε} n) space. Compared to the fastest previously known result (Chan, 2013), our data structure reduces the space usage by O(log n) without increasing the query time.
Cite as
Yakov Nekrich. Four-Dimensional Dominance Range Reporting in Linear Space. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{nekrich:LIPIcs.SoCG.2020.59,
author = {Nekrich, Yakov},
title = {{Four-Dimensional Dominance Range Reporting in Linear Space}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {59:1--59:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.59},
URN = {urn:nbn:de:0030-drops-122170},
doi = {10.4230/LIPIcs.SoCG.2020.59},
annote = {Keywords: Range searching, geometric data structures, word RAM}
}
Document
Radon Numbers Grow Linearly
Abstract
Define the k-th Radon number r_k of a convexity space as the smallest number (if it exists) for which any set of r_k points can be partitioned into k parts whose convex hulls intersect. Combining the recent abstract fractional Helly theorem of Holmsen and Lee with earlier methods of Bukh, we prove that r_k grows linearly, i.e., r_k ≤ c(r₂)⋅ k.
Cite as
Dömötör Pálvölgyi. Radon Numbers Grow Linearly. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 60:1-60:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{palvolgyi:LIPIcs.SoCG.2020.60,
author = {P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r},
title = {{Radon Numbers Grow Linearly}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {60:1--60:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.60},
URN = {urn:nbn:de:0030-drops-122183},
doi = {10.4230/LIPIcs.SoCG.2020.60},
annote = {Keywords: discrete geometry, convexity space, Radon number}
}
Document
Bounding Radon Number via Betti Numbers
Abstract
We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem.
More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex.
Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface.
Cite as
Zuzana Patáková. Bounding Radon Number via Betti Numbers. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{patakova:LIPIcs.SoCG.2020.61,
author = {Pat\'{a}kov\'{a}, Zuzana},
title = {{Bounding Radon Number via Betti Numbers}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {61:1--61:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.61},
URN = {urn:nbn:de:0030-drops-122198},
doi = {10.4230/LIPIcs.SoCG.2020.61},
annote = {Keywords: Radon number, topological complexity, constrained chain maps, fractional Helly theorem, convexity spaces}
}
Document
Barycentric Cuts Through a Convex Body
Abstract
Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question.
It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3.
Cite as
Zuzana Patáková, Martin Tancer, and Uli Wagner. Barycentric Cuts Through a Convex Body. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{patakova_et_al:LIPIcs.SoCG.2020.62,
author = {Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
title = {{Barycentric Cuts Through a Convex Body}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {62:1--62:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.62},
URN = {urn:nbn:de:0030-drops-122201},
doi = {10.4230/LIPIcs.SoCG.2020.62},
annote = {Keywords: convex body, barycenter, Tukey depth, smooth manifold, critical points}
}
Document
Sketched MinDist
Abstract
We sketch geometric objects J as vectors through the MinDist function, setting the i-th coordinate v_i(J) = inf_{p ∈ J} ‖p-q_i‖ for q_i ∈ Q from a point set Q. Building a vector from these coordinate values induces a simple, effective, and powerful distance: the Euclidean distance between these sketch vectors. This paper shows how large this set Q needs to be under a variety of shapes and scenarios. For hyperplanes we provide direct connection to the sensitivity sampling framework, so relative error can be preserved in d dimensions using |Q| = O(d/ε²). However, for other shapes, we show we need to enforce a minimum distance parameter ρ, and a domain size L. For d=2 the sample size Q then can be Õ((L/ρ) ⋅ 1/ε²). For objects (e.g., trajectories) with at most k pieces this can provide stronger for all approximations with Õ((L/ρ)⋅ k³ / ε²) points. Moreover, with similar size bounds and restrictions, such trajectories can be reconstructed exactly using only these sketch vectors. Cumulatively, these results demonstrate that these MinDist sketch vectors provide an effective and efficient shape model, a compact representation, and a precise representation of geometric objects.
Cite as
Jeff M. Phillips and Pingfan Tang. Sketched MinDist. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{phillips_et_al:LIPIcs.SoCG.2020.63,
author = {Phillips, Jeff M. and Tang, Pingfan},
title = {{Sketched MinDist}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {63:1--63:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.63},
URN = {urn:nbn:de:0030-drops-122218},
doi = {10.4230/LIPIcs.SoCG.2020.63},
annote = {Keywords: curve similarity, sensitivity sampling, sketching}
}
Document
Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis
Abstract
We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the 1-dimensional homology classes with ℤ₂ coefficients in a given simplicial complex K. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al. [Dey et al., 2018], runs in O(N^ω + N² g) time, where N denotes the number of simplices in K, g denotes the rank of the 1-homology group of K, and ω denotes the exponent of matrix multiplication. In this paper, we present two conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex K. The first algorithm runs in Õ(m^ω) time, where m denotes the number of edges in K, whereas the second algorithm runs in O(m^ω + N m^{ω-1}) time.
We also study the problem of finding a minimum cycle basis in an undirected graph G with n vertices and m edges. The best known algorithm for this problem runs in O(m^ω) time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in Õ(m^ω) time.
Cite as
Abhishek Rathod. Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 64:1-64:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{rathod:LIPIcs.SoCG.2020.64,
author = {Rathod, Abhishek},
title = {{Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {64:1--64:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.64},
URN = {urn:nbn:de:0030-drops-122223},
doi = {10.4230/LIPIcs.SoCG.2020.64},
annote = {Keywords: Computational topology, Minimum homology basis, Minimum cycle basis, Simplicial complexes, Matrix computations}
}
Document
Dense Graphs Have Rigid Parts
Abstract
While the problem of determining whether an embedding of a graph G in ℝ² is infinitesimally rigid is well understood, specifying whether a given embedding of G is rigid or not is still a hard task that usually requires ad hoc arguments. In this paper, we show that every embedding (not necessarily generic) of a dense enough graph (concretely, a graph with at least C₀n^{3/2}(log n)^β edges, for some absolute constants C₀>0 and β), which satisfies some very mild general position requirements (no three vertices of G are embedded to a common line), must have a subframework of size at least three which is rigid. For the proof we use a connection, established in Raz [Discrete Comput. Geom., 2017], between the notion of graph rigidity and configurations of lines in ℝ³. This connection allows us to use properties of line configurations established in Guth and Katz [Annals Math., 2015]. In fact, our proof requires an extended version of Guth and Katz result; the extension we need is proved by János Kollár in an Appendix to our paper.
We do not know whether our assumption on the number of edges being Ω(n^{3/2}log n) is tight, and we provide a construction that shows that requiring Ω(n log n) edges is necessary.
Cite as
Orit E. Raz and József Solymosi. Dense Graphs Have Rigid Parts. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{raz_et_al:LIPIcs.SoCG.2020.65,
author = {Raz, Orit E. and Solymosi, J\'{o}zsef},
title = {{Dense Graphs Have Rigid Parts}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {65:1--65:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.65},
URN = {urn:nbn:de:0030-drops-122236},
doi = {10.4230/LIPIcs.SoCG.2020.65},
annote = {Keywords: Graph rigidity, line configurations in 3D}
}
Document
Incidences Between Points and Curves with Almost Two Degrees of Freedom
Abstract
We study incidences between points and (constant-degree algebraic) curves in three dimensions, taken from a family C of curves that have almost two degrees of freedom, meaning that (i) every pair of curves of C intersect in O(1) points, (ii) for any pair of points p, q, there are only O(1) curves of C that pass through both points, and (iii) a pair p, q of points admit a curve of C that passes through both of them if and only if F(p,q)=0 for some polynomial F of constant degree associated with the problem. (As an example, the family of unit circles in ℝ³ that pass through some fixed point is such a family.)
We begin by studying two specific instances of this scenario. The first instance deals with the case of unit circles in ℝ³ that pass through some fixed point (so called anchored unit circles). In the second case we consider tangencies between directed points and circles in the plane, where a directed point is a pair (p,u), where p is a point in the plane and u is a direction, and (p,u) is tangent to a circle γ if p ∈ γ and u is the direction of the tangent to γ at p. A lifting transformation due to Ellenberg et al. maps these tangencies to incidences between points and curves ("lifted circles") in three dimensions. In both instances we have a family of curves in ℝ³ with almost two degrees of freedom.
We show that the number of incidences between m points and n anchored unit circles in ℝ³, as well as the number of tangencies between m directed points and n arbitrary circles in the plane, is O(m^(3/5)n^(3/5)+m+n) in both cases.
We then derive a similar incidence bound, with a few additional terms, for more general families of curves in ℝ³ with almost two degrees of freedom, under a few additional natural assumptions.
The proofs follow standard techniques, based on polynomial partitioning, but they face a critical novel issue involving the analysis of surfaces that are infinitely ruled by the respective family of curves, as well as of surfaces in a dual three-dimensional space that are infinitely ruled by the respective family of suitably defined dual curves. We either show that no such surfaces exist, or develop and adapt techniques for handling incidences on such surfaces.
The general bound that we obtain is O(m^(3/5)n^(3/5)+m+n) plus additional terms that depend on how many curves or dual curves can lie on an infinitely-ruled surface.
Cite as
Micha Sharir and Oleg Zlydenko. Incidences Between Points and Curves with Almost Two Degrees of Freedom. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{sharir_et_al:LIPIcs.SoCG.2020.66,
author = {Sharir, Micha and Zlydenko, Oleg},
title = {{Incidences Between Points and Curves with Almost Two Degrees of Freedom}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {66:1--66:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.66},
URN = {urn:nbn:de:0030-drops-122244},
doi = {10.4230/LIPIcs.SoCG.2020.66},
annote = {Keywords: Incidences, Polynomial partition, Degrees of freedom, Infinitely-ruled surfaces, Three dimensions}
}
Document
Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)
Abstract
Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity.
For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem.
Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).
Cite as
Uli Wagner and Emo Welzl. Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{wagner_et_al:LIPIcs.SoCG.2020.67,
author = {Wagner, Uli and Welzl, Emo},
title = {{Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {67:1--67:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.67},
URN = {urn:nbn:de:0030-drops-122259},
doi = {10.4230/LIPIcs.SoCG.2020.67},
annote = {Keywords: triangulation, flip graph, graph connectivity, associahedron, subdivision, convex decomposition, flippable edge, flip complex, regular triangulation, bistellar flip graph, secondary polytope, polyhedral subdivision}
}
Document
On the Planar Two-Center Problem and Circular Hulls
Abstract
Given a set S of n points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of S. Previously, Eppstein [SODA'97] gave a randomized algorithm of O(nlog²n) expected time and Chan [CGTA'99] presented a deterministic algorithm of O(nlog² nlog²log n) time. In this paper, we propose an O(nlog² n) time deterministic algorithm, which improves Chan’s deterministic algorithm and matches the randomized bound of Eppstein. If S is in convex position, we solve the problem in O(nlog nlog log n) deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.
Cite as
Haitao Wang. On the Planar Two-Center Problem and Circular Hulls. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{wang:LIPIcs.SoCG.2020.68,
author = {Wang, Haitao},
title = {{On the Planar Two-Center Problem and Circular Hulls}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {68:1--68:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.68},
URN = {urn:nbn:de:0030-drops-122267},
doi = {10.4230/LIPIcs.SoCG.2020.68},
annote = {Keywords: two-center, disk coverage, circular hulls, dynamic data structures}
}
Document
Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments
Abstract
In this paper, we first consider the subpath convex hull query problem: Given a simple path π of n vertices, preprocess it so that the convex hull of any query subpath of π can be quickly obtained. Previously, Guibas, Hershberger, and Snoeyink [SODA 90'] proposed a data structure of O(n) space and O(log n log log n) query time; reducing the query time to O(log n) increases the space to O(nlog log n). We present an improved result that uses O(n) space while achieving O(log n) query time. Like the previous work, our query algorithm returns a compact interval tree representing the convex hull so that standard binary-search-based queries on the hull can be performed in O(log n) time each. Our new result leads to improvements for several other problems.
In particular, with the help of the above result, we present new algorithms for the ray-shooting problem among segments. Given a set of n (possibly intersecting) line segments in the plane, preprocess it so that the first segment hit by a query ray can be quickly found. We give a data structure of O(n log n) space that can answer each query in (√n log n) time. If the segments are nonintersecting or if the segments are lines, then the space can be reduced to O(n). All these are classical problems that have been studied extensively. Previously data structures of Õ(√n) query time were known in early 1990s; nearly no progress has been made for over two decades. For all problems, our results provide improvements by reducing the space of the data structures by at least a logarithmic factor while the preprocessing and query times are the same as before or even better.
Cite as
Haitao Wang. Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{wang:LIPIcs.SoCG.2020.69,
author = {Wang, Haitao},
title = {{Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {69:1--69:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.69},
URN = {urn:nbn:de:0030-drops-122275},
doi = {10.4230/LIPIcs.SoCG.2020.69},
annote = {Keywords: subpath hull queries, convex hulls, compact interval trees, ray-shooting, data structures}
}
Document
GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes
Abstract
The computation of Vietoris-Rips persistence barcodes is both execution-intensive and memory-intensive. In this paper, we study the computational structure of Vietoris-Rips persistence barcodes, and identify several unique mathematical properties and algorithmic opportunities with connections to the GPU. Mathematically and empirically, we look into the properties of apparent pairs, which are independently identifiable persistence pairs comprising up to 99% of persistence pairs. We give theoretical upper and lower bounds of the apparent pair rate and model the average case. We also design massively parallel algorithms to take advantage of the very large number of simplices that can be processed independently of each other. Having identified these opportunities, we develop a GPU-accelerated software for computing Vietoris-Rips persistence barcodes, called Ripser++. The software achieves up to 30x speedup over the total execution time of the original Ripser and also reduces CPU-memory usage by up to 2.0x. We believe our GPU-acceleration based efforts open a new chapter for the advancement of topological data analysis in the post-Moore’s Law era.
Cite as
Simon Zhang, Mengbai Xiao, and Hao Wang. GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 70:1-70:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{zhang_et_al:LIPIcs.SoCG.2020.70,
author = {Zhang, Simon and Xiao, Mengbai and Wang, Hao},
title = {{GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {70:1--70:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.70},
URN = {urn:nbn:de:0030-drops-122287},
doi = {10.4230/LIPIcs.SoCG.2020.70},
annote = {Keywords: Parallel Algorithms, Topological Data Analysis, Vietoris-Rips, Persistent Homology, Apparent Pairs, High Performance Computing, GPU, Random Graphs}
}
Document
Media Exposition
The Spiroplot App (Media Exposition)
Abstract
We introduce an app for generating spiroplots, based on a new discrete-time, linear, dynamic system that repeatedly rotates a pair of points, and plots points where they land. The app supports easy definition of the initial situation and has various visualization settings. It can be accessed at https://spiroplot.sites.uu.nl.
Cite as
Casper van Dommelen, Marc van Kreveld, and Jérôme Urhausen. The Spiroplot App (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 71:1-71:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{vandommelen_et_al:LIPIcs.SoCG.2020.71,
author = {van Dommelen, Casper and van Kreveld, Marc and Urhausen, J\'{e}r\^{o}me},
title = {{The Spiroplot App}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {71:1--71:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.71},
URN = {urn:nbn:de:0030-drops-122292},
doi = {10.4230/LIPIcs.SoCG.2020.71},
annote = {Keywords: generative art, dynamic system, pattern generation tool}
}
Document
Media Exposition
Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition)
Abstract
In this video, we present theoretical and practical methods for achieving arbitrary reconfiguration of a set of objects, based on the use of external forces, such as a magnetic field or gravity: Upon actuation, each object is pushed in the same direction. This concept can be used for a wide range of applications in which particles do not have their own energy supply or in which they are subject to the same global control commands.
A crucial challenge for achieving any desired target configuration is breaking global symmetry in a controlled fashion. Previous work (some of which was presented during SoCG 2015) made use of specifically placed barriers; however, introducing precisely located obstacles into the workspace is impractical for many scenarios. In this paper, we present a different, less intrusive method: making use of the interplay between static friction with a boundary and the external force to achieve arbitrary reconfiguration. Our key contributions are theoretical characterizations of the critical coefficient of friction that is sufficient for rearranging two particles in triangles, convex polygons, and regular polygons; a method for reconfiguring multiple particles in rectangular workspaces, and deriving practical algorithms for these rearrangements. Hardware experiments show the efficacy of these procedures, demonstrating the usefulness of this novel approach.
Cite as
Victor M. Baez, Aaron T. Becker, Sándor P. Fekete, and Arne Schmidt. Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 72:1-72:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{baez_et_al:LIPIcs.SoCG.2020.72,
author = {Baez, Victor M. and Becker, Aaron T. and Fekete, S\'{a}ndor P. and Schmidt, Arne},
title = {{Coordinated Particle Relocation with Global Signals and Local Friction}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {72:1--72:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.72},
URN = {urn:nbn:de:0030-drops-122305},
doi = {10.4230/LIPIcs.SoCG.2020.72},
annote = {Keywords: Global control, reconfiguration, geometric algorithms, friction}
}
Document
Media Exposition
Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition)
Abstract
In this video, we consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility. We present algorithmic methods that are able to detect and reconfigure arbitrary polyominoes, based on finite-state robots, while also preserving connectivity of a structure during reconfiguration. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.
Cite as
Amira Abdel-Rahman, Aaron T. Becker, Daniel E. Biediger, Kenneth C. Cheung, Sándor P. Fekete, Neil A. Gershenfeld, Sabrina Hugo, Benjamin Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Michael Yannuzzi. Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 73:1-73:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{abdelrahman_et_al:LIPIcs.SoCG.2020.73,
author = {Abdel-Rahman, Amira and Becker, Aaron T. and Biediger, Daniel E. and Cheung, Kenneth C. and Fekete, S\'{a}ndor P. and Gershenfeld, Neil A. and Hugo, Sabrina and Jenett, Benjamin and Keldenich, Phillip and Niehs, Eike and Rieck, Christian and Schmidt, Arne and Scheffer, Christian and Yannuzzi, Michael},
title = {{Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {73:1--73:6},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.73},
URN = {urn:nbn:de:0030-drops-122310},
doi = {10.4230/LIPIcs.SoCG.2020.73},
annote = {Keywords: Finite automata, reconfiguration, construction, scaling}
}
Document
Media Exposition
How to Make a CG Video (Media Exposition)
Abstract
In this video we describe why producing a Computational Geometry video is a good idea, what it takes to make one, and how to actually do it. This includes a guide for the overall process, a number of examples, and a variety of tips and tricks.
Cite as
Aaron T. Becker and Sándor P. Fekete. How to Make a CG Video (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 74:1-74:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{becker_et_al:LIPIcs.SoCG.2020.74,
author = {Becker, Aaron T. and Fekete, S\'{a}ndor P.},
title = {{How to Make a CG Video}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {74:1--74:6},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.74},
URN = {urn:nbn:de:0030-drops-122328},
doi = {10.4230/LIPIcs.SoCG.2020.74},
annote = {Keywords: Videos, animation, education, SoCG Multimedia}
}
Document
Media Exposition
Covering Rectangles by Disks: The Video (Media Exposition)
Abstract
In this video, we motivate and visualize a fundamental result for covering a rectangle by a set of non-uniform circles: For any λ ≥ 1, the critical covering area A^*(λ) is the minimum value for which any set of disks with total area at least A^*(λ) can cover a rectangle of dimensions λ× 1. We show that there is a threshold value λ₂ = √(√7/2 - 1/4) ≈ 1.035797…, such that for λ < λ₂ the critical covering area A^*(λ) is A^*(λ) = 3π(λ²/16 + 5/32 + 9/256λ²), and for λ ≥ λ₂, the critical area is A^*(λ) = π(λ²+2)/4; these values are tight. For the special case λ=1, i.e., for covering a unit square, the critical covering area is 195π/256 ≈ 2.39301…. We describe the structure of the proof, and show animations of some of the main components.
Cite as
Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Covering Rectangles by Disks: The Video (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 75:1-75:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{fekete_et_al:LIPIcs.SoCG.2020.75,
author = {Fekete, S\'{a}ndor P. and Keldenich, Phillip and Scheffer, Christian},
title = {{Covering Rectangles by Disks: The Video}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {75:1--75:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.75},
URN = {urn:nbn:de:0030-drops-122337},
doi = {10.4230/LIPIcs.SoCG.2020.75},
annote = {Keywords: Disk covering, critical density, covering coefficient, tight worst-case bound, interval arithmetic, approximation}
}
Document
Media Exposition
Step-By-Step Straight Skeletons (Media Exposition)
Abstract
We present two software packages for computing straight skeletons: Monos, our implementation of an algorithm by Biedl et al. (2015), computes the straight skeleton of a monotone input polygon, and Surfer2 implements a generalization of an algorithm by Aichholzer and Aurenhammer (1998) to handle multiplicatively-weighted planar straight-line graphs as input.
The graphical user interfaces that ship with our codes support step-by-step computations, where each event can be investigated and studied by the user. This makes them a canonical candidate for educational purposes and detailed event analyses. Both codes are freely available on GitHub.
Cite as
Günther Eder, Martin Held, and Peter Palfrader. Step-By-Step Straight Skeletons (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 76:1-76:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{eder_et_al:LIPIcs.SoCG.2020.76,
author = {Eder, G\"{u}nther and Held, Martin and Palfrader, Peter},
title = {{Step-By-Step Straight Skeletons}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {76:1--76:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.76},
URN = {urn:nbn:de:0030-drops-122343},
doi = {10.4230/LIPIcs.SoCG.2020.76},
annote = {Keywords: weighted straight skeleton, implementation, visualization, graphical user interface, education}
}
Document
Media Exposition
Computing Animations of Linkages with Rotational Symmetry (Media Exposition)
Abstract
We present a piece of software for computing animations of linkages with rotational symmetry in the plane. We construct these linkages from an algorithm that utilises a special type of edge colouring to embed graphs with rotational symmetry.
Cite as
Sean Dewar, Georg Grasegger, and Jan Legerský. Computing Animations of Linkages with Rotational Symmetry (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 77:1-77:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{dewar_et_al:LIPIcs.SoCG.2020.77,
author = {Dewar, Sean and Grasegger, Georg and Legersk\'{y}, Jan},
title = {{Computing Animations of Linkages with Rotational Symmetry}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {77:1--77:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.77},
URN = {urn:nbn:de:0030-drops-122356},
doi = {10.4230/LIPIcs.SoCG.2020.77},
annote = {Keywords: Flexibility, Linkages, Symmetry}
}
Document
Media Exposition
Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)
Abstract
Face-connected configurations of cubes are a common model for modular robots in three dimensions. In this abstract and the accompanying video we study reconfigurations of such modular robots using so-called sliding moves. Using sliding moves, it is always possible to reconfigure one face-connected configuration of n cubes into any other, while keeping the robot connected at all stages of the reconfiguration. For certain configurations Ω(n²) sliding moves are necessary. In contrast, the best current upper bound is O(n³). It has been conjectured that there is always a cube on the outside of any face-connected configuration of cubes which can be moved without breaking connectivity. The existence of such a cube would immediately imply a straight-forward O(n²) reconfiguration algorithm. However, we present a configuration of cubes such that no cube on the outside can move without breaking connectivity. In other words, we show that this particular avenue towards an O(n²) reconfiguration algorithm for face-connected cubes is blocked.
Cite as
Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, and Jules Wulms. Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 78:1-78:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{miltzow_et_al:LIPIcs.SoCG.2020.78,
author = {Miltzow, Tillmann and Parada, Irene and Sonke, Willem and Speckmann, Bettina and Wulms, Jules},
title = {{Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {78:1--78:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.78},
URN = {urn:nbn:de:0030-drops-122363},
doi = {10.4230/LIPIcs.SoCG.2020.78},
annote = {Keywords: Sliding cubes, Reconfiguration, Modular robots}
}
Document
Media Exposition
Dots & Polygons (Media Exposition)
Abstract
We present a new game, Dots & Polygons, played on a planar point set. We prove that its NP-hard and discuss strategies for the case when the point set is in convex position.
Cite as
Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten. Dots & Polygons (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 79:1-79:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{buchin_et_al:LIPIcs.SoCG.2020.79,
author = {Buchin, Kevin and Hagedoorn, Mart and Kostitsyna, Irina and van Mulken, Max and Rensen, Jolan and van Schooten, Leo},
title = {{Dots \& Polygons}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {79:1--79:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.79},
URN = {urn:nbn:de:0030-drops-122371},
doi = {10.4230/LIPIcs.SoCG.2020.79},
annote = {Keywords: Dots \& Boxes, NP-hard, game, cycle packing}
}
Document
Media Exposition
Designing Art Galleries (Media Exposition)
Abstract
We present a method for generating interesting levels based on several NP-hardness reductions for a puzzle game based on the Art Gallery problem.
Cite as
Toon van Benthem, Kevin Buchin, Irina Kostitsyna, and Stijn Slot. Designing Art Galleries (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 80:1-80:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{vanbenthem_et_al:LIPIcs.SoCG.2020.80,
author = {van Benthem, Toon and Buchin, Kevin and Kostitsyna, Irina and Slot, Stijn},
title = {{Designing Art Galleries}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {80:1--80:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.80},
URN = {urn:nbn:de:0030-drops-122382},
doi = {10.4230/LIPIcs.SoCG.2020.80},
annote = {Keywords: Art Gallery problem, NP-hard, puzzle, level generation}
}
Document
Media Exposition
Plane-Filling Trails (Media Exposition)
Abstract
The order in which plane-filling curves visit points in the plane can be exploited to design efficient algorithms. Typically, the curves are useful because they preserve locality: points that are close to each other along the curve tend to be close to each other in the plane, and vice versa. However, sketches of plane-filling curves do not show this well: they are hard to read on different levels of detail and it is hard to see how far apart points are along the curve. This paper presents a software tool to produce compelling visualisations that may give more insight in the structure of the curves.
Cite as
Herman Haverkort. Plane-Filling Trails (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 81:1-81:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{haverkort:LIPIcs.SoCG.2020.81,
author = {Haverkort, Herman},
title = {{Plane-Filling Trails}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {81:1--81:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.81},
URN = {urn:nbn:de:0030-drops-122396},
doi = {10.4230/LIPIcs.SoCG.2020.81},
annote = {Keywords: space-filling curve, plane-filling curve, spatial indexing}
}
Document
Media Exposition
Visual Demo of Discrete Stratified Morse Theory (Media Exposition)
Abstract
Discrete stratified Morse theory, first introduced by Knudson and Wang, works toward a discrete analogue of Goresky and MacPherson’s stratified Morse theory. It is inspired by the works of Forman on discrete Morse theory by generalizing stratified Morse theory to finite simplicial complexes. The class of discrete stratified Morse functions is much larger than that of discrete Morse functions. Any arbitrary real-valued function defined on a finite simplicial complex can be made into a discrete stratified Morse function with the proper stratification of the underlying complex. An algorithm is given by Knudson and Wang that constructs a discrete stratified Morse function on any finite simplicial complex equipped with an arbitrary real-valued function. Our media contribution is an open-sourced visualization tool that implements such an algorithm for 2-complexes embedded in the plane, and provides an interactive demo for users to explore the algorithmic process and to perform homotopy-preserving simplification of the resulting stratified complex.
Cite as
Youjia Zhou, Kevin Knudson, and Bei Wang. Visual Demo of Discrete Stratified Morse Theory (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 82:1-82:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{zhou_et_al:LIPIcs.SoCG.2020.82,
author = {Zhou, Youjia and Knudson, Kevin and Wang, Bei},
title = {{Visual Demo of Discrete Stratified Morse Theory}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {82:1--82:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.82},
URN = {urn:nbn:de:0030-drops-122409},
doi = {10.4230/LIPIcs.SoCG.2020.82},
annote = {Keywords: Discrete Morse theory, stratified Morse theory, discrete stratified Morse theory, topological data analysis, data visualization}
}
Document
CG Challenge
Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)
Abstract
The Minimum Convex Partition problem (MCP) is a problem in which a point-set is used as the vertices for a planar subdivision, whose number of edges is to be minimized. In this planar subdivision, the outer face is the convex hull of the point-set, and the interior faces are convex. In this paper, we discuss and implement the approach to this problem using randomized local search, and different initialization techniques based on maximizing collinearity. We also solve small instances optimally using a SAT formulation. We explored this as part of the 2020 Computational Geometry Challenge, where we placed first as Team UBC.
Cite as
Da Wei Zheng, Jack Spalding-Jamieson, and Brandon Zhang. Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 83:1-83:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{zheng_et_al:LIPIcs.SoCG.2020.83,
author = {Zheng, Da Wei and Spalding-Jamieson, Jack and Zhang, Brandon},
title = {{Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {83:1--83:7},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.83},
URN = {urn:nbn:de:0030-drops-122412},
doi = {10.4230/LIPIcs.SoCG.2020.83},
annote = {Keywords: convex partition, randomized local search, planar point sets}
}
Document
CG Challenge
Computing Low-Cost Convex Partitions for Planar Point Sets Based on a Memetic Approach (CG Challenge)
Abstract
We present a memetic approach designed to tackle the 2020 Computational Geometry Challenge on the Minimum Convex Partition problem. It is based on a simple local search algorithm hybridized with a genetic approach. The population is brought down to its smallest possible size - only 2 individuals - for a very simple implementation. This algorithm was applied to all the instances, without any specific parameterization or adaptation.
Cite as
Laurent Moalic, Dominique Schmitt, Julien Lepagnot, and Julien Kritter. Computing Low-Cost Convex Partitions for Planar Point Sets Based on a Memetic Approach (CG Challenge). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 84:1-84:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{moalic_et_al:LIPIcs.SoCG.2020.84,
author = {Moalic, Laurent and Schmitt, Dominique and Lepagnot, Julien and Kritter, Julien},
title = {{Computing Low-Cost Convex Partitions for Planar Point Sets Based on a Memetic Approach}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {84:1--84:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.84},
URN = {urn:nbn:de:0030-drops-122423},
doi = {10.4230/LIPIcs.SoCG.2020.84},
annote = {Keywords: metaheuristics, memetic algorithms, convex partition optimization}
}
Document
CG Challenge
Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions (CG Challenge)
Abstract
Our work on minimum convex decompositions is based on two key components: (1) different strategies for computing initial decompositions, partly adapted to the characteristics of the input data, and (2) local optimizations for reducing the number of convex faces of a decomposition. We discuss our main heuristics and show how they helped to reduce the face count.
Cite as
Günther Eder, Martin Held, Stefan de Lorenzo, and Peter Palfrader. Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions (CG Challenge). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 85:1-85:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{eder_et_al:LIPIcs.SoCG.2020.85,
author = {Eder, G\"{u}nther and Held, Martin and de Lorenzo, Stefan and Palfrader, Peter},
title = {{Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {85:1--85:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Cabello, Sergio and Chen, Danny Z.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.85},
URN = {urn:nbn:de:0030-drops-122438},
doi = {10.4230/LIPIcs.SoCG.2020.85},
annote = {Keywords: Computational Geometry, geometric optimization, algorithm engineering, convex decomposition}
}