Volume
LIPIcs, Volume 129
35th International Symposium on Computational Geometry (SoCG 2019)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG)
Event
SoCG 2019, June 18-21, 2019, Portland, Oregon, USAEditors
Publication Details
- published at: 2019-06-11
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-104-7
- DBLP: db/conf/compgeom/compgeom2019
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 129, SoCG'19, Complete Volume
Abstract
LIPIcs, Volume 129, SoCG'19, Complete Volume
Cite as
35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@Proceedings{barequet_et_al:LIPIcs.SoCG.2019,
title = {{LIPIcs, Volume 129, SoCG'19, Complete Volume}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019},
URN = {urn:nbn:de:0030-drops-105562},
doi = {10.4230/LIPIcs.SoCG.2019},
annote = {Keywords: Theory of computation, Computational geometry, Design and analysis of algorithms, Mathematics of computing, Combinatorics, Graph algortihms}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{barequet_et_al:LIPIcs.SoCG.2019.0,
author = {Barequet, Gill and Wang, Yusu},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {0:i--0:xvi},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.0},
URN = {urn:nbn:de:0030-drops-104047},
doi = {10.4230/LIPIcs.SoCG.2019.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
A Geometric Data Structure from Neuroscience (Invited Talk)
Abstract
An intriguing geometric primitive, "expand-and-sparsify", has been found in the olfactory system of the fly and several other organisms. It maps an input vector to a much higher-dimensional sparse representation, using a random linear transformation followed by winner-take-all thresholding.
I will show that this representation has a variety of formal properties, such as locality preservation, that make it an attractive data structure for algorithms and machine learning. In particular, mimicking the fly’s circuitry yields algorithms for similarity search and for novelty detection that have provable guarantees as well as having practical performance that is competitive with state-of-the-art methods.
This talk is based on work with Saket Navlakha (Salk Institute), Chuck Stevens (Salk Institute), and Chris Tosh (Columbia).
Cite as
Sanjoy Dasgupta. A Geometric Data Structure from Neuroscience (Invited Talk). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{dasgupta:LIPIcs.SoCG.2019.1,
author = {Dasgupta, Sanjoy},
title = {{A Geometric Data Structure from Neuroscience}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.1},
URN = {urn:nbn:de:0030-drops-104055},
doi = {10.4230/LIPIcs.SoCG.2019.1},
annote = {Keywords: Geometric data structure, algorithm design, neuroscience}
}
Document
Invited Talk
Some Geometric and Computational Challenges Arising in Structural Molecular Biology (Invited Talk)
Abstract
Computational protein design is a transformative field with exciting prospects for advancing both basic science and translational medical research. New algorithms blend discrete and continuous geometry to address the challenges of creating designer proteins. I will discuss recent progress in this area and some interesting open problems.
I will motivate this talk by discussing how, by using continuous geometric representations within a discrete optimization framework, broadly-neutralizing anti-HIV-1 antibodies were computationally designed that are now being tested in humans - the designed antibodies are currently in eight clinical trials, one of which is Phase 2a (NCT03721510). These continuous representations model the flexibility and dynamics of biological macromolecules, which are an important structural determinant of function.
However, reconstruction of biomolecular dynamics from experimental observables requires the determination of a conformational probability distribution. These distributions are not fully constrained by the limited geometric information from experiments, making the problem ill-posed in the sense of Hadamard. The ill-posed nature of the problem comes from the fact that it has no unique solution. Multiple or even an infinite number of solutions may exist. To avoid the ill-posed nature, the problem must be regularized by making (hopefully reasonable) assumptions.
I will present new ways to both represent and visualize correlated inter-domain protein motions. We use Bingham distributions, based on a quaternion fit to circular moments of a physics-based quadratic form. To find the optimal solution for the distribution, we designed an efficient, provable branch-and-bound algorithm that exploits the structure of analytical solutions to the trigonometric moment problem. Hence, continuous conformational PDFs can be determined directly from NMR measurements. The representation works especially well for multi-domain systems with broad conformational distributions. For more information please see Y. Qi et al. Jour. Mol. Biol. 2018; 430(18 Pt B):3412-3426. doi: 10.1016/j.jmb.2018.06.022.
Ultimately, this method has parallels to other branches of geometric computing that balance discrete and continuous representations, including physical geometric algorithms, robotics, computational geometry, and robust optimization. I will advocate for using continuous distributions for protein modeling, and describe future work and open problems.
Cite as
Bruce R. Donald. Some Geometric and Computational Challenges Arising in Structural Molecular Biology (Invited Talk). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{donald:LIPIcs.SoCG.2019.2,
author = {Donald, Bruce R.},
title = {{Some Geometric and Computational Challenges Arising in Structural Molecular Biology}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {2:1--2:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.2},
URN = {urn:nbn:de:0030-drops-104065},
doi = {10.4230/LIPIcs.SoCG.2019.2},
annote = {Keywords: Geometric computing, combutational biology, Continuous Interdomain Orientation Distributions of Protein Conformations}
}
Document
A New Lower Bound for Semigroup Orthogonal Range Searching
Abstract
We report the first improvement in the space-time trade-off of lower bounds for the orthogonal range searching problem in the semigroup model, since Chazelle’s result from 1990. This is one of the very fundamental problems in range searching with a long history. Previously, Andrew Yao’s influential result had shown that the problem is already non-trivial in one dimension [Yao, 1982]: using m units of space, the query time Q(n) must be Omega(alpha(m,n) + n/(m-n+1)) where alpha(*,*) is the inverse Ackermann’s function, a very slowly growing function. In d dimensions, Bernard Chazelle [Chazelle, 1990] proved that the query time must be Q(n) = Omega((log_beta n)^{d-1}) where beta = 2m/n. Chazelle’s lower bound is known to be tight for when space consumption is "high" i.e., m = Omega(n log^{d+epsilon}n).
We have two main results. The first is a lower bound that shows Chazelle’s lower bound was not tight for "low space": we prove that we must have m Q(n) = Omega(n (log n log log n)^{d-1}). Our lower bound does not close the gap to the existing data structures, however, our second result is that our analysis is tight. Thus, we believe the gap is in fact natural since lower bounds are proven for idempotent semigroups while the data structures are built for general semigroups and thus they cannot assume (and use) the properties of an idempotent semigroup. As a result, we believe to close the gap one must study lower bounds for non-idempotent semigroups or building data structures for idempotent semigroups. We develope significantly new ideas for both of our results that could be useful in pursuing either of these directions.
Cite as
Peyman Afshani. A New Lower Bound for Semigroup Orthogonal Range Searching. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{afshani:LIPIcs.SoCG.2019.3,
author = {Afshani, Peyman},
title = {{A New Lower Bound for Semigroup Orthogonal Range Searching}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {3:1--3:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.3},
URN = {urn:nbn:de:0030-drops-104075},
doi = {10.4230/LIPIcs.SoCG.2019.3},
annote = {Keywords: Data Structures, Range Searching, Lower bounds}
}
Document
Independent Range Sampling, Revisited Again
Abstract
We revisit the range sampling problem: the input is a set of points where each point is associated with a real-valued weight. The goal is to store them in a structure such that given a query range and an integer k, we can extract k independent random samples from the points inside the query range, where the probability of sampling a point is proportional to its weight.
This line of work was initiated in 2014 by Hu, Qiao, and Tao and it was later followed up by Afshani and Wei. The first line of work mostly studied unweighted but dynamic version of the problem in one dimension whereas the second result considered the static weighted problem in one dimension as well as the unweighted problem in 3D for halfspace queries.
We offer three main results and some interesting insights that were missed by the previous work: We show that it is possible to build efficient data structures for range sampling queries if we allow the query time to hold in expectation (the first result), or obtain efficient worst-case query bounds by allowing the sampling probability to be approximately proportional to the weight (the second result). The third result is a conditional lower bound that shows essentially one of the previous two concessions is needed. For instance, for the 3D range sampling queries, the first two results give efficient data structures with near-linear space and polylogarithmic query time whereas the lower bound shows with near-linear space the worst-case query time must be close to n^{2/3}, ignoring polylogarithmic factors. Up to our knowledge, this is the first such major gap between the expected and worst-case query time of a range searching problem.
Cite as
Peyman Afshani and Jeff M. Phillips. Independent Range Sampling, Revisited Again. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{afshani_et_al:LIPIcs.SoCG.2019.4,
author = {Afshani, Peyman and Phillips, Jeff M.},
title = {{Independent Range Sampling, Revisited Again}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {4:1--4:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.4},
URN = {urn:nbn:de:0030-drops-104088},
doi = {10.4230/LIPIcs.SoCG.2019.4},
annote = {Keywords: Range Searching, Data Structures, Sampling}
}
Document
An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Abstract
In 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in R^d and if D >= 1 is an integer, then there is a d-variate polynomial P of degree at most D so that each connected component of R^d \ Z(P) intersects O(n/D^{d-g}) sets from S. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently - the expected running time of our algorithm is linear in |S|. Our approach exploits the technique of quantifier elimination combined with that of epsilon-samples.
We present four applications of our result. The first is a data structure for answering point-enclosure queries among a family of semi-algebraic sets in R^d in O(log n) time, with storage complexity and expected preprocessing time of O(n^{d+epsilon}). The second is a data structure for answering range search queries with semi-algebraic ranges in O(log n) time, with O(n^{t+epsilon}) storage and expected preprocessing time, where t > 0 is an integer that depends on d and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semi-algebraic sets in R^{d} in O(log^2 n) time, with O(n^{d+epsilon}) storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic planar curves into pseudo-segments.
Cite as
Pankaj K. Agarwal, Boris Aronov, Esther Ezra, and Joshua Zahl. An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.5,
author = {Agarwal, Pankaj K. and Aronov, Boris and Ezra, Esther and Zahl, Joshua},
title = {{An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {5:1--5:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.5},
URN = {urn:nbn:de:0030-drops-104096},
doi = {10.4230/LIPIcs.SoCG.2019.5},
annote = {Keywords: Polynomial partitioning, quantifier elimination, semi-algebraic range spaces, epsilon-samples}
}
Document
Efficient Algorithms for Geometric Partial Matching
Abstract
Let A and B be two point sets in the plane of sizes r and n respectively (assume r <= n), and let k be a parameter. A matching between A and B is a family of pairs in A x B so that any point of A cup B appears in at most one pair. Given two positive integers p and q, we define the cost of matching M to be c(M) = sum_{(a, b) in M}||a-b||_p^q where ||*||_p is the L_p-norm. The geometric partial matching problem asks to find the minimum-cost size-k matching between A and B.
We present efficient algorithms for geometric partial matching problem that work for any powers of L_p-norm matching objective: An exact algorithm that runs in O((n + k^2)polylog n) time, and a (1 + epsilon)-approximation algorithm that runs in O((n + k sqrt{k})polylog n * log epsilon^{-1}) time. Both algorithms are based on the primal-dual flow augmentation scheme; the main improvements involve using dynamic data structures to achieve efficient flow augmentations. With similar techniques, we give an exact algorithm for the planar transportation problem running in O(min{n^2, rn^{3/2}}polylog n) time.
Cite as
Pankaj K. Agarwal, Hsien-Chih Chang, and Allen Xiao. Efficient Algorithms for Geometric Partial Matching. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.6,
author = {Agarwal, Pankaj K. and Chang, Hsien-Chih and Xiao, Allen},
title = {{Efficient Algorithms for Geometric Partial Matching}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {6:1--6:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.6},
URN = {urn:nbn:de:0030-drops-104109},
doi = {10.4230/LIPIcs.SoCG.2019.6},
annote = {Keywords: partial matching, transportation, optimal transport, minimum-cost flow, bichromatic closest pair}
}
Document
Connecting the Dots (with Minimum Crossings)
Abstract
We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection L subseteq Lines(P)={l: l is a line segment with both endpoints in P}, and a non-negative integer k, decide if there is a subcollection L'subseteq L such that the graph G=(P,L') is isomorphic to a graph in F and L' has at most k crossings. By G=(P,L'), we refer to the graph on vertex set P, where two vertices are adjacent if and only if there is a line segment that connects them in L'. Intuitively, in Crossing Minimization, we have a set of locations of interest, and we want to build/draw/exhibit connections between them (where L indicates where it is feasible to have these connections) so that we obtain a structure in F. Natural choices for F are the collections of perfect matchings, Hamiltonian paths, and graphs that contain an (s,t)-path (a path whose endpoints are labeled). While the objective of seeking a solution with few crossings is of interest from a theoretical point of view, it is also well motivated by a wide range of practical considerations. For example, links/roads (such as highways) may be cheaper to build and faster to traverse, and signals/moving objects would collide/interrupt each other less often. Further, graphs with fewer crossings are preferred for graphic user interfaces.
As a starting point for a systematic study, we consider a special case of Crossing Minimization. Already for this case, we obtain NP-hardness and W[1]-hardness results, and ETH-based lower bounds. Specifically, suppose that the input also contains a collection D of d non-crossing line segments such that each point in P belongs to exactly one line in D, and L does not contain line segments between points on the same line in D. Clearly, Crossing Minimization is the case where d=n - then, P is in general position. The case of d=2 is of interest not only because it is the most restricted non-trivial case, but also since it corresponds to a class of graphs that has been well studied - specifically, it is Crossing Minimization where G=(P,L) is a (bipartite) graph with a so called two-layer drawing. For d=2, we consider three basic choices of F. For perfect matchings, we show (i) NP-hardness with an ETH-based lower bound, (ii) solvability in subexponential parameterized time, and (iii) existence of an O(k^2)-vertex kernel. Second, for Hamiltonian paths, we show (i) solvability in subexponential parameterized time, and (ii) existence of an O(k^2)-vertex kernel. Lastly, for graphs that contain an (s,t)-path, we show (i) NP-hardness and W[1]-hardness, and (ii) membership in XP.
Cite as
Akanksha Agrawal, Grzegorz Guśpiel, Jayakrishnan Madathil, Saket Saurabh, and Meirav Zehavi. Connecting the Dots (with Minimum Crossings). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{agrawal_et_al:LIPIcs.SoCG.2019.7,
author = {Agrawal, Akanksha and Gu\'{s}piel, Grzegorz and Madathil, Jayakrishnan and Saurabh, Saket and Zehavi, Meirav},
title = {{Connecting the Dots (with Minimum Crossings)}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {7:1--7:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.7},
URN = {urn:nbn:de:0030-drops-104117},
doi = {10.4230/LIPIcs.SoCG.2019.7},
annote = {Keywords: crossing minimization, parameterized complexity, FPT algorithm, polynomial kernel, W\lbrack1\rbrack-hardness}
}
Document
General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem
Abstract
We consider the classical camera pose estimation problem that arises in many computer vision applications, in which we are given n 2D-3D correspondences between points in the scene and points in the camera image (some of which are incorrect associations), and where we aim to determine the camera pose (the position and orientation of the camera in the scene) from this data. We demonstrate that this posing problem can be reduced to the problem of computing epsilon-approximate incidences between two-dimensional surfaces (derived from the input correspondences) and points (on a grid) in a four-dimensional pose space. Similar reductions can be applied to other camera pose problems, as well as to similar problems in related application areas.
We describe and analyze three techniques for solving the resulting epsilon-approximate incidences problem in the context of our camera posing application. The first is a straightforward assignment of surfaces to the cells of a grid (of side-length epsilon) that they intersect. The second is a variant of a primal-dual technique, recently introduced by a subset of the authors [Aiger et al., 2017] for different (and simpler) applications. The third is a non-trivial generalization of a data structure Fonseca and Mount [Da Fonseca and Mount, 2010], originally designed for the case of hyperplanes. We present and analyze this technique in full generality, and then apply it to the camera posing problem at hand.
We compare our methods experimentally on real and synthetic data. Our experiments show that for the typical values of n and epsilon, the primal-dual method is the fastest, also in practice.
Cite as
Dror Aiger, Haim Kaplan, Efi Kokiopoulou, Micha Sharir, and Bernhard Zeisl. General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{aiger_et_al:LIPIcs.SoCG.2019.8,
author = {Aiger, Dror and Kaplan, Haim and Kokiopoulou, Efi and Sharir, Micha and Zeisl, Bernhard},
title = {{General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {8:1--8:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.8},
URN = {urn:nbn:de:0030-drops-104129},
doi = {10.4230/LIPIcs.SoCG.2019.8},
annote = {Keywords: Camera positioning, Approximate incidences, Incidences}
}
Document
Circumscribing Polygons and Polygonizations for Disjoint Line Segments
Abstract
Given a planar straight-line graph G=(V,E) in R^2, a circumscribing polygon of G is a simple polygon P whose vertex set is V, and every edge in E is either an edge or an internal diagonal of P. A circumscribing polygon is a polygonization for G if every edge in E is an edge of P.
We prove that every arrangement of n disjoint line segments in the plane has a subset of size Omega(sqrt{n}) that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to R^3.
We show that it is NP-complete to decide whether a given graph G admits a circumscribing polygon, even if G is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization.
Cite as
Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, and Csaba D. Tóth. Circumscribing Polygons and Polygonizations for Disjoint Line Segments. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{akitaya_et_al:LIPIcs.SoCG.2019.9,
author = {Akitaya, Hugo A. and Korman, Matias and Rudoy, Mikhail and Souvaine, Diane L. and T\'{o}th, Csaba D.},
title = {{Circumscribing Polygons and Polygonizations for Disjoint Line Segments}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {9:1--9:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.9},
URN = {urn:nbn:de:0030-drops-104136},
doi = {10.4230/LIPIcs.SoCG.2019.9},
annote = {Keywords: circumscribing polygon, Hamiltonicity, extremal combinatorics}
}
Document
Morphing Contact Representations of Graphs
Abstract
We consider the problem of morphing between contact representations of a plane graph. In a contact representation of a plane graph, vertices are realized by internally disjoint elements from a family of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in the graph. In a morph between two contact representations we insist that at each time step (continuously throughout the morph) we have a contact representation of the same type.
We focus on the case when the geometric objects are triangles that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs.
We study piecewise linear morphs, where each step is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. We provide a polynomial-time algorithm that decides whether there is a piecewise linear morph between two RT-representations of a plane triangulation, and, if so, computes a morph with a quadratic number of linear morphs. As a direct consequence, we obtain that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the "top-most" triangle in both representations corresponds to the same vertex. This shows that the realization space of such RT-representations of any 4-connected plane triangulation forms a connected set.
Cite as
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, and Vincenzo Roselli. Morphing Contact Representations of Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{angelini_et_al:LIPIcs.SoCG.2019.10,
author = {Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano and Roselli, Vincenzo},
title = {{Morphing Contact Representations of Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {10:1--10:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.10},
URN = {urn:nbn:de:0030-drops-104145},
doi = {10.4230/LIPIcs.SoCG.2019.10},
annote = {Keywords: Contact representations, Triangulations, Planar morphs, Schnyder woods}
}
Document
When Convexity Helps Collapsing Complexes
Abstract
This paper illustrates how convexity hypotheses help collapsing simplicial complexes. We first consider a collection of compact convex sets and show that the nerve of the collection is collapsible whenever the union of sets in the collection is convex. We apply this result to prove that the Delaunay complex of a finite point set is collapsible. We then consider a convex domain defined as the convex hull of a finite point set. We show that if the point set samples sufficiently densely the domain, then both the Cech complex and the Rips complex of the point set are collapsible for a well-chosen scale parameter. A key ingredient in our proofs consists in building a filtration by sweeping space with a growing sphere whose center has been fixed and studying events occurring through the filtration. Since the filtration mimics the sublevel sets of a Morse function with a single critical point, we anticipate this work to lay the foundations for a non-smooth, discrete Morse Theory.
Cite as
Dominique Attali, André Lieutier, and David Salinas. When Convexity Helps Collapsing Complexes. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{attali_et_al:LIPIcs.SoCG.2019.11,
author = {Attali, Dominique and Lieutier, Andr\'{e} and Salinas, David},
title = {{When Convexity Helps Collapsing Complexes}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.11},
URN = {urn:nbn:de:0030-drops-104152},
doi = {10.4230/LIPIcs.SoCG.2019.11},
annote = {Keywords: collapsibility, convexity, collection of compact convex sets, nerve, filtration, Delaunay complex, Cech complex, Rips complex}
}
Document
Optimal Algorithm for Geodesic Farthest-Point Voronoi Diagrams
Abstract
Let P be a simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. Given a set S of m sites being a subset of the vertices of P, we present the first randomized algorithm to compute the geodesic farthest-point Voronoi diagram of S in P running in expected O(n + m) time. That is, a partition of P into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic distance. This algorithm can be extended to run in expected O(n + m log m) time when S is an arbitrary set of m sites contained in P.
Cite as
Luis Barba. Optimal Algorithm for Geodesic Farthest-Point Voronoi Diagrams. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{barba:LIPIcs.SoCG.2019.12,
author = {Barba, Luis},
title = {{Optimal Algorithm for Geodesic Farthest-Point Voronoi Diagrams}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {12:1--12:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.12},
URN = {urn:nbn:de:0030-drops-104161},
doi = {10.4230/LIPIcs.SoCG.2019.12},
annote = {Keywords: Geodesic distance, simple polygons, farthest-point Voronoi diagram}
}
Document
Upward Book Embeddings of st-Graphs
Abstract
We study k-page upward book embeddings (kUBEs) of st-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on k pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a kUBE is NP-complete for k >= 3. A hardness result for this problem was previously known only for k = 6 [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on k=2. On the algorithmic side, we present polynomial-time algorithms for testing the existence of 2UBEs of planar st-graphs with branchwidth b and of plane st-graphs whose faces have a special structure. These algorithms run in O(f(b)* n+n^3) time and O(n) time, respectively, where f is a singly-exponential function on b. Moreover, on the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving 2UBE.
Cite as
Carla Binucci, Giordano Da Lozzo, Emilio Di Giacomo, Walter Didimo, Tamara Mchedlidze, and Maurizio Patrignani. Upward Book Embeddings of st-Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{binucci_et_al:LIPIcs.SoCG.2019.13,
author = {Binucci, Carla and Da Lozzo, Giordano and Di Giacomo, Emilio and Didimo, Walter and Mchedlidze, Tamara and Patrignani, Maurizio},
title = {{Upward Book Embeddings of st-Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {13:1--13:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.13},
URN = {urn:nbn:de:0030-drops-104170},
doi = {10.4230/LIPIcs.SoCG.2019.13},
annote = {Keywords: Upward Book Embeddings, st-Graphs, SPQR-trees, Branchwidth, Sphere-cut Decomposition}
}
Document
Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12
Abstract
We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c >= 13 and d >= 1, we give first explicit constructions of c-crossing-critical graphs containing a vertex of degree greater than d. We also show that such unbounded degree constructions do not exist for c <=12, precisely, that there exists a constant D such that every c-crossing-critical graph with c <=12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.
Cite as
Drago Bokal, Zdeněk Dvořák, Petr Hliněný, Jesús Leaños, Bojan Mohar, and Tilo Wiedera. Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{bokal_et_al:LIPIcs.SoCG.2019.14,
author = {Bokal, Drago and Dvo\v{r}\'{a}k, Zden\v{e}k and Hlin\v{e}n\'{y}, Petr and Lea\~{n}os, Jes\'{u}s and Mohar, Bojan and Wiedera, Tilo},
title = {{Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c \langle= 12}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.14},
URN = {urn:nbn:de:0030-drops-104183},
doi = {10.4230/LIPIcs.SoCG.2019.14},
annote = {Keywords: graph drawing, crossing number, crossing-critical, zip product}
}
Document
Preconditioning for the Geometric Transportation Problem
Abstract
In the geometric transportation problem, we are given a collection of points P in d-dimensional Euclidean space, and each point is given a supply of mu(p) units of mass, where mu(p) could be a positive or a negative integer, and the total sum of the supplies is 0. The goal is to find a flow (called a transportation map) that transports mu(p) units from any point p with mu(p) > 0, and transports -mu(p) units into any point p with mu(p) < 0. Moreover, the flow should minimize the total distance traveled by the transported mass. The optimal value is known as the transportation cost, or the Earth Mover’s Distance (from the points with positive supply to those with negative supply). This problem has been widely studied in many fields of computer science: from theoretical work in computational geometry, to applications in computer vision, graphics, and machine learning.
In this work we study approximation algorithms for the geometric transportation problem. We give an algorithm which, for any fixed dimension d, finds a (1+epsilon)-approximate transportation map in time nearly-linear in n, and polynomial in epsilon^{-1} and in the logarithm of the total supply. This is the first approximation scheme for the problem whose running time depends on n as n * polylog(n). Our techniques combine the generalized preconditioning framework of Sherman, which is grounded in continuous optimization, with simple geometric arguments to first reduce the problem to a minimum cost flow problem on a sparse graph, and then to design a good preconditioner for this latter problem.
Cite as
Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov. Preconditioning for the Geometric Transportation Problem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{khesin_et_al:LIPIcs.SoCG.2019.15,
author = {Khesin, Andrey Boris and Nikolov, Aleksandar and Paramonov, Dmitry},
title = {{Preconditioning for the Geometric Transportation Problem}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {15:1--15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.15},
URN = {urn:nbn:de:0030-drops-104190},
doi = {10.4230/LIPIcs.SoCG.2019.15},
annote = {Keywords: Earth Mover Distance, Transportation Problem, Minimum Cost Flow}
}
Document
The One-Way Communication Complexity of Dynamic Time Warping Distance
Abstract
We resolve the randomized one-way communication complexity of Dynamic Time Warping (DTW) distance. We show that there is an efficient one-way communication protocol using O~(n/alpha) bits for the problem of computing an alpha-approximation for DTW between strings x and y of length n, and we prove a lower bound of Omega(n / alpha) bits for the same problem. Our communication protocol works for strings over an arbitrary metric of polynomial size and aspect ratio, and we optimize the logarithmic factors depending on properties of the underlying metric, such as when the points are low-dimensional integer vectors equipped with various metrics or have bounded doubling dimension. We also consider linear sketches of DTW, showing that such sketches must have size Omega(n).
Cite as
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, and Lin F. Yang. The One-Way Communication Complexity of Dynamic Time Warping Distance. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{braverman_et_al:LIPIcs.SoCG.2019.16,
author = {Braverman, Vladimir and Charikar, Moses and Kuszmaul, William and Woodruff, David P. and Yang, Lin F.},
title = {{The One-Way Communication Complexity of Dynamic Time Warping Distance}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {16:1--16:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.16},
URN = {urn:nbn:de:0030-drops-104203},
doi = {10.4230/LIPIcs.SoCG.2019.16},
annote = {Keywords: dynamic time warping, one-way communication complexity, tree metrics}
}
Document
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
Abstract
The Fréchet distance provides a natural and intuitive measure for the popular task of computing the similarity of two (polygonal) curves. While a simple algorithm computes it in near-quadratic time, a strongly subquadratic algorithm cannot exist unless the Strong Exponential Time Hypothesis fails. Still, fast practical implementations of the Fréchet distance, in particular for realistic input curves, are highly desirable. This has even lead to a designated competition, the ACM SIGSPATIAL GIS Cup 2017: Here, the challenge was to implement a near-neighbor data structure under the Fréchet distance. The bottleneck of the top three implementations turned out to be precisely the decision procedure for the Fréchet distance.
In this work, we present a fast, certifying implementation for deciding the Fréchet distance, in order to (1) complement its pessimistic worst-case hardness by an empirical analysis on realistic input data and to (2) improve the state of the art for the GIS Cup challenge. We experimentally evaluate our implementation on a large benchmark consisting of several data sets (including handwritten characters and GPS trajectories). Compared to the winning implementation of the GIS Cup, we obtain running time improvements of up to more than two orders of magnitude for the decision procedure and of up to a factor of 30 for queries to the near-neighbor data structure.
Cite as
Karl Bringmann, Marvin Künnemann, and André Nusser. Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{bringmann_et_al:LIPIcs.SoCG.2019.17,
author = {Bringmann, Karl and K\"{u}nnemann, Marvin and Nusser, Andr\'{e}},
title = {{Walking the Dog Fast in Practice: Algorithm Engineering of the Fr\'{e}chet Distance}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {17:1--17:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.17},
URN = {urn:nbn:de:0030-drops-104219},
doi = {10.4230/LIPIcs.SoCG.2019.17},
annote = {Keywords: curve simplification, Fr\'{e}chet distance, algorithm engineering}
}
Document
Polyline Simplification has Cubic Complexity
Abstract
In the classic polyline simplification problem we want to replace a given polygonal curve P, consisting of n vertices, by a subsequence P' of k vertices from P such that the polygonal curves P and P' are "close". Closeness is usually measured using the Hausdorff or Fréchet distance. These distance measures can be applied globally, i.e., to the whole curves P and P', or locally, i.e., to each simplified subcurve and the line segment that it was replaced with separately (and then taking the maximum). We provide an O(n^3) time algorithm for simplification under Global-Fréchet distance, improving the previous best algorithm by a factor of Omega(kn^2). We also provide evidence that in high dimensions cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Fréchet, and Global-Fréchet). Specifically, improving the cubic time to O(n^{3-epsilon} poly(d)) for polyline simplification over (R^d,L_p) for p = 1 would violate plausible conjectures. We obtain similar results for all p in [1,infty), p != 2. In total, in high dimensions and over general L_p-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Fréchet, and Global-Fréchet, by providing new algorithms and conditional lower bounds.
Cite as
Karl Bringmann and Bhaskar Ray Chaudhury. Polyline Simplification has Cubic Complexity. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{bringmann_et_al:LIPIcs.SoCG.2019.18,
author = {Bringmann, Karl and Chaudhury, Bhaskar Ray},
title = {{Polyline Simplification has Cubic Complexity}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {18:1--18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.18},
URN = {urn:nbn:de:0030-drops-104224},
doi = {10.4230/LIPIcs.SoCG.2019.18},
annote = {Keywords: Polyline simplification, Fr\'{e}chet distance, Hausdorff distance, Conditional lower bounds}
}
Document
A Spanner for the Day After
Abstract
We show how to construct (1+epsilon)-spanner over a set P of n points in R^d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters theta, epsilon in (0,1), the computed spanner G has O(epsilon^{-7d} log^7 epsilon^{-1} * theta^{-6} n log n (log log n)^6) edges. Furthermore, for any k, and any deleted set B subseteq P of k points, the residual graph G \ B is (1+epsilon)-spanner for all the points of P except for (1+theta)k of them. No previous constructions, beyond the trivial clique with O(n^2) edges, were known such that only a tiny additional fraction (i.e., theta) lose their distance preserving connectivity.
Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one dimensional construction in a black box fashion.
Cite as
Kevin Buchin, Sariel Har-Peled, and Dániel Oláh. A Spanner for the Day After. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{buchin_et_al:LIPIcs.SoCG.2019.19,
author = {Buchin, Kevin and Har-Peled, Sariel and Ol\'{a}h, D\'{a}niel},
title = {{A Spanner for the Day After}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {19:1--19:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.19},
URN = {urn:nbn:de:0030-drops-104237},
doi = {10.4230/LIPIcs.SoCG.2019.19},
annote = {Keywords: Geometric spanners, vertex failures, robustness}
}
Document
Computing Shapley Values in the Plane
Abstract
We consider the problem of computing Shapley values for points in the plane, where each point is interpreted as a player, and the value of a coalition is defined by the area of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box.
For sets of n points in the plane, we show how to compute in roughly O(n^{3/2}) time the Shapley values for the area of the minimum axis-parallel bounding box and the area of the union of the rectangles spanned by the origin and the input points. When the points form an increasing or decreasing chain, the running time can be improved to near-linear. In all these cases, we use linearity of the Shapley values and algebraic methods.
We also show that Shapley values for the area of the convex hull or the minimum enclosing disk can be computed in O(n^2) and O(n^3) time, respectively. These problems are closely related to the model of stochastic point sets considered in computational geometry, but here we have to consider random insertion orders of the points instead of a probabilistic existence of points.
Cite as
Sergio Cabello and Timothy M. Chan. Computing Shapley Values in the Plane. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{cabello_et_al:LIPIcs.SoCG.2019.20,
author = {Cabello, Sergio and Chan, Timothy M.},
title = {{Computing Shapley Values in the Plane}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {20:1--20:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.20},
URN = {urn:nbn:de:0030-drops-104244},
doi = {10.4230/LIPIcs.SoCG.2019.20},
annote = {Keywords: Shapley values, stochastic computational geometry, convex hull, minimum enclosing disk, bounding box, arrangements, convolutions, airport problem}
}
Document
On the Metric Distortion of Embedding Persistence Diagrams into Separable Hilbert Spaces
Abstract
Persistence diagrams are important descriptors in Topological Data Analysis. Due to the nonlinearity of the space of persistence diagrams equipped with their diagram distances, most of the recent attempts at using persistence diagrams in machine learning have been done through kernel methods, i.e., embeddings of persistence diagrams into Reproducing Kernel Hilbert Spaces, in which all computations can be performed easily. Since persistence diagrams enjoy theoretical stability guarantees for the diagram distances, the metric properties of the feature map, i.e., the relationship between the Hilbert distance and the diagram distances, are of central interest for understanding if the persistence diagram guarantees carry over to the embedding. In this article, we study the possibility of embedding persistence diagrams into separable Hilbert spaces with bi-Lipschitz maps. In particular, we show that for several stable embeddings into infinite-dimensional Hilbert spaces defined in the literature, any lower bound must depend on the cardinalities of the persistence diagrams, and that when the Hilbert space is finite dimensional, finding a bi-Lipschitz embedding is impossible, even when restricting the persistence diagrams to have bounded cardinalities.
Cite as
Mathieu Carrière and Ulrich Bauer. On the Metric Distortion of Embedding Persistence Diagrams into Separable Hilbert Spaces. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{carriere_et_al:LIPIcs.SoCG.2019.21,
author = {Carri\`{e}re, Mathieu and Bauer, Ulrich},
title = {{On the Metric Distortion of Embedding Persistence Diagrams into Separable Hilbert Spaces}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {21:1--21:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.21},
URN = {urn:nbn:de:0030-drops-104259},
doi = {10.4230/LIPIcs.SoCG.2019.21},
annote = {Keywords: Topological Data Analysis, Persistence Diagrams, Hilbert space embedding}
}
Document
Convex Polygons in Cartesian Products
Abstract
We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of n real numbers (for short, grid). First, we prove that every such grid contains a convex polygon with Omega(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d in N), and obtain a tight lower bound of Omega(log^{d-1}n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the longest convex polygonal chain in a grid that contains no two points with the same x- or y-coordinate. We show that the maximum size of such a convex polygon can be efficiently approximated up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
Cite as
Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot. Convex Polygons in Cartesian Products. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{decarufel_et_al:LIPIcs.SoCG.2019.22,
author = {De Carufel, Jean-Lou and Dumitrescu, Adrian and Meulemans, Wouter and Ophelders, Tim and Pennarun, Claire and T\'{o}th, Csaba D. and Verdonschot, Sander},
title = {{Convex Polygons in Cartesian Products}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {22:1--22:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.22},
URN = {urn:nbn:de:0030-drops-104267},
doi = {10.4230/LIPIcs.SoCG.2019.22},
annote = {Keywords: Erd\H{o}s-Szekeres theorem, Cartesian product, convexity, polyhedron, recursive construction, approximation algorithm}
}
Document
Smallest k-Enclosing Rectangle Revisited
Abstract
Given a set of n points in the plane, and a parameter k, we consider the problem of computing the minimum (perimeter or area) axis-aligned rectangle enclosing k points. We present the first near quadratic time algorithm for this problem, improving over the previous near-O(n^{5/2})-time algorithm by Kaplan et al. [Haim Kaplan et al., 2017]. We provide an almost matching conditional lower bound, under the assumption that (min,+)-convolution cannot be solved in truly subquadratic time. Furthermore, we present a new reduction (for either perimeter or area) that can make the time bound sensitive to k, giving near O(n k) time. We also present a near linear time (1+epsilon)-approximation algorithm to the minimum area of the optimal rectangle containing k points. In addition, we study related problems including the 3-sided, arbitrarily oriented, weighted, and subset sum versions of the problem.
Cite as
Timothy M. Chan and Sariel Har-Peled. Smallest k-Enclosing Rectangle Revisited. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{chan_et_al:LIPIcs.SoCG.2019.23,
author = {Chan, Timothy M. and Har-Peled, Sariel},
title = {{Smallest k-Enclosing Rectangle Revisited}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {23:1--23:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.23},
URN = {urn:nbn:de:0030-drops-104276},
doi = {10.4230/LIPIcs.SoCG.2019.23},
annote = {Keywords: Geometric optimization, outliers, approximation algorithms, conditional lower bounds}
}
Document
Dynamic Geometric Data Structures via Shallow Cuttings
Abstract
We present new results on a number of fundamental problems about dynamic geometric data structures:
1) We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1-center of a 2D point set, (v) the number of maximal (i.e., skyline) points in a 3D point set. The update times are near n^{11/12} for (i) and (ii), n^{7/8} for (iii) and (iv), and n^{2/3} for (v). Previously, sublinear bounds were known only for restricted "semi-online" settings [Chan, SODA 2002].
2) We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is O(log^2n), and the amortized update time is O(log^4n) instead of O(log^5n) [Chan, SODA 2006; Kaplan et al., SODA 2017].
3) We also improve previous fully dynamic data structures for maintaining the bichromatic closest pair between two 2D point sets and the diameter of a 2D point set. The amortized update time is O(log^4n) instead of O(log^7n) [Eppstein 1995; Chan, SODA 2006; Kaplan et al., SODA 2017].
Cite as
Timothy M. Chan. Dynamic Geometric Data Structures via Shallow Cuttings. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{chan:LIPIcs.SoCG.2019.24,
author = {Chan, Timothy M.},
title = {{Dynamic Geometric Data Structures via Shallow Cuttings}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {24:1--24:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.24},
URN = {urn:nbn:de:0030-drops-104288},
doi = {10.4230/LIPIcs.SoCG.2019.24},
annote = {Keywords: dynamic data structures, convex hulls, nearest neighbor search, closest pair, shallow cuttings}
}
Document
Lower Bounds for Electrical Reduction on Surfaces
Abstract
We strengthen the connections between electrical transformations and homotopy from the planar setting - observed and studied since Steinitz - to arbitrary surfaces with punctures. As a result, we improve our earlier lower bound on the number of electrical transformations required to reduce an n-vertex graph on surface in the worst case [SOCG 2016] in two different directions. Our previous Omega(n^{3/2}) lower bound applies only to facial electrical transformations on plane graphs with no terminals. First we provide a stronger Omega(n^2) lower bound when the planar graph has two or more terminals, which follows from a quadratic lower bound on the number of homotopy moves in the annulus. Our second result extends our earlier Omega(n^{3/2}) lower bound to the wider class of planar electrical transformations, which preserve the planarity of the graph but may delete cycles that are not faces of the given embedding. This new lower bound follow from the observation that the defect of the medial graph of a planar graph is the same for all its planar embeddings.
Cite as
Hsien-Chih Chang, Marcos Cossarini, and Jeff Erickson. Lower Bounds for Electrical Reduction on Surfaces. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{chang_et_al:LIPIcs.SoCG.2019.25,
author = {Chang, Hsien-Chih and Cossarini, Marcos and Erickson, Jeff},
title = {{Lower Bounds for Electrical Reduction on Surfaces}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {25:1--25:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.25},
URN = {urn:nbn:de:0030-drops-104294},
doi = {10.4230/LIPIcs.SoCG.2019.25},
annote = {Keywords: electrical transformation, Delta-Y-transformation, homotopy, tight, defect, SPQR-tree, smoothings, routing set, 2-flipping}
}
Document
Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead
Abstract
We present efficient data structures for problems on unit discs and arcs of their boundary in the plane. (i) We give an output-sensitive algorithm for the dynamic maintenance of the union of n unit discs under insertions in O(k log^2 n) update time and O(n) space, where k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. (ii) As part of the solution of (i) we devise a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines, which we believe is of independent interest. The structure has O(log^2 n) update time and O(log n) vertical ray shooting query time. To achieve this performance, we devise a new algorithm for finding the intersection between two lower envelopes of pseudo-lines in O(log n) time, using tentative binary search; the lower envelopes are special in that at x=-infty any pseudo-line contributing to the first envelope lies below every pseudo-line contributing to the second envelope. (iii) We also present a dynamic range searching structure for a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), where the ranges are unit discs, with O(n log n) preprocessing time, O(n^{1/2+epsilon} + l) query time and O(log^2 n) amortized update time, where l is the size of the output and for any epsilon>0. The structure requires O(n) storage space.
Cite as
Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer. Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.26,
author = {Agarwal, Pankaj K. and Cohen, Ravid and Halperin, Dan and Mulzer, Wolfgang},
title = {{Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {26:1--26:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.26},
URN = {urn:nbn:de:0030-drops-104307},
doi = {10.4230/LIPIcs.SoCG.2019.26},
annote = {Keywords: lower envelopes, pseudo-lines, unit discs, range search, dynamic algorithms, tentative binary search}
}
Document
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
Abstract
We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem.
A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus g has a cut graph of length at most a given value. We prove a time lower bound for this problem of n^{Omega(g/log g)} conditionally to ETH. In other words, the first n^{O(g)}-time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year old question of these authors.
A multiway cut of an undirected graph G with t distinguished vertices, called terminals, is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n^{Omega(sqrt{gt + g^2}/log(gt))}, conditionally to ETH, for any choice of the genus g >=0 of the graph and the number of terminals t >=4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case).
Reductions to planar problems usually involve a grid-like structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value g of the genus.
Cite as
Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{cohenaddad_et_al:LIPIcs.SoCG.2019.27,
author = {Cohen-Addad, Vincent and Colin de Verdi\`{e}re, \'{E}ric and Marx, D\'{a}niel and de Mesmay, Arnaud},
title = {{Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {27:1--27:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.27},
URN = {urn:nbn:de:0030-drops-104311},
doi = {10.4230/LIPIcs.SoCG.2019.27},
annote = {Keywords: Cut graph, Multiway cut, Surface, Lower bound, Parameterized Complexity, Exponential Time Hypothesis}
}
Document
The VC Dimension of Metric Balls Under Fréchet and Hausdorff Distances
Abstract
The Vapnik-Chervonenkis dimension provides a notion of complexity for systems of sets. If the VC dimension is small, then knowing this can drastically simplify fundamental computational tasks such as classification, range counting, and density estimation through the use of sampling bounds. We analyze set systems where the ground set X is a set of polygonal curves in R^d and the sets {R} are metric balls defined by curve similarity metrics, such as the Fréchet distance and the Hausdorff distance, as well as their discrete counterparts. We derive upper and lower bounds on the VC dimension that imply useful sampling bounds in the setting that the number of curves is large, but the complexity of the individual curves is small. Our upper bounds are either near-quadratic or near-linear in the complexity of the curves that define the ranges and they are logarithmic in the complexity of the curves that define the ground set.
Cite as
Anne Driemel, Jeff M. Phillips, and Ioannis Psarros. The VC Dimension of Metric Balls Under Fréchet and Hausdorff Distances. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{driemel_et_al:LIPIcs.SoCG.2019.28,
author = {Driemel, Anne and Phillips, Jeff M. and Psarros, Ioannis},
title = {{The VC Dimension of Metric Balls Under Fr\'{e}chet and Hausdorff Distances}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {28:1--28:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.28},
URN = {urn:nbn:de:0030-drops-104329},
doi = {10.4230/LIPIcs.SoCG.2019.28},
annote = {Keywords: VC dimension, Fr\'{e}chet distance, Hausdorff distance}
}
Document
Dual Circumference and Collinear Sets
Abstract
We show that, if an n-vertex triangulation T of maximum degree Delta has a dual that contains a cycle of length l, then T has a non-crossing straight-line drawing in which some set, called a collinear set, of Omega(l/Delta^4) vertices lie on a line. Using the current lower bounds on the length of longest cycles in 3-regular 3-connected graphs, this implies that every n-vertex planar graph of maximum degree Delta has a collinear set of size Omega(n^{0.8}/Delta^4). Very recently, Dujmović et al. (SODA 2019) showed that, if S is a collinear set in a triangulation T then, for any point set X subset R^2 with |X|=|S|, T has a non-crossing straight-line drawing in which the vertices of S are drawn on the points in X. Because of this, collinear sets have numerous applications in graph drawing and related areas.
Cite as
Vida Dujmović and Pat Morin. Dual Circumference and Collinear Sets. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{dujmovic_et_al:LIPIcs.SoCG.2019.29,
author = {Dujmovi\'{c}, Vida and Morin, Pat},
title = {{Dual Circumference and Collinear Sets}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {29:1--29:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.29},
URN = {urn:nbn:de:0030-drops-104338},
doi = {10.4230/LIPIcs.SoCG.2019.29},
annote = {Keywords: Planar graphs, collinear sets, untangling, column planarity, universal point subsets, partial simultaneous geometric drawings}
}
Document
A Product Inequality for Extreme Distances
Abstract
Let p_1,...,p_n be n distinct points in the plane, and assume that the minimum inter-point distance occurs s_{min} times, while the maximum inter-point distance occurs s_{max} times. It is shown that s_{min} s_{max} <= (9/8)n^2 + O(n); this settles a conjecture of Erdős and Pach (1990).
Cite as
Adrian Dumitrescu. A Product Inequality for Extreme Distances. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{dumitrescu:LIPIcs.SoCG.2019.30,
author = {Dumitrescu, Adrian},
title = {{A Product Inequality for Extreme Distances}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {30:1--30:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.30},
URN = {urn:nbn:de:0030-drops-104343},
doi = {10.4230/LIPIcs.SoCG.2019.30},
annote = {Keywords: Extreme distances, repeated distances}
}
Document
Topological Data Analysis in Information Space
Abstract
Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context.
Cite as
Herbert Edelsbrunner, Žiga Virk, and Hubert Wagner. Topological Data Analysis in Information Space. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2019.31,
author = {Edelsbrunner, Herbert and Virk, \v{Z}iga and Wagner, Hubert},
title = {{Topological Data Analysis in Information Space}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {31:1--31:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.31},
URN = {urn:nbn:de:0030-drops-104357},
doi = {10.4230/LIPIcs.SoCG.2019.31},
annote = {Keywords: Computational topology, persistent homology, information theory, entropy}
}
Document
Cubic Planar Graphs That Cannot Be Drawn On Few Lines
Abstract
For every integer l, we construct a cubic 3-vertex-connected planar bipartite graph G with O(l^3) vertices such that there is no planar straight-line drawing of G whose vertices all lie on l lines. This strengthens previous results on graphs that cannot be drawn on few lines, which constructed significantly larger maximal planar graphs. We also find apex-trees and cubic bipartite series-parallel graphs that cannot be drawn on a bounded number of lines.
Cite as
David Eppstein. Cubic Planar Graphs That Cannot Be Drawn On Few Lines. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{eppstein:LIPIcs.SoCG.2019.32,
author = {Eppstein, David},
title = {{Cubic Planar Graphs That Cannot Be Drawn On Few Lines}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {32:1--32:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.32},
URN = {urn:nbn:de:0030-drops-104363},
doi = {10.4230/LIPIcs.SoCG.2019.32},
annote = {Keywords: graph drawing, universal point sets, collinearity}
}
Document
Counting Polygon Triangulations is Hard
Abstract
We prove that it is #P-complete to count the triangulations of a (non-simple) polygon.
Cite as
David Eppstein. Counting Polygon Triangulations is Hard. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{eppstein:LIPIcs.SoCG.2019.33,
author = {Eppstein, David},
title = {{Counting Polygon Triangulations is Hard}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {33:1--33:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.33},
URN = {urn:nbn:de:0030-drops-104371},
doi = {10.4230/LIPIcs.SoCG.2019.33},
annote = {Keywords: counting complexity, #P-completeness, triangulation, polygons}
}
Document
Topologically Trivial Closed Walks in Directed Surface Graphs
Abstract
Let G be a directed graph with n vertices and m edges, embedded on a surface S, possibly with boundary, with first Betti number beta. We consider the complexity of finding closed directed walks in G that are either contractible (trivial in homotopy) or bounding (trivial in integer homology) in S. Specifically, we describe algorithms to determine whether G contains a simple contractible cycle in O(n+m) time, or a contractible closed walk in O(n+m) time, or a bounding closed walk in O(beta (n+m)) time. Our algorithms rely on subtle relationships between strong connectivity in G and in the dual graph G^*; our contractible-closed-walk algorithm also relies on a seminal topological result of Hass and Scott. We also prove that detecting simple bounding cycles is NP-hard.
We also describe three polynomial-time algorithms to compute shortest contractible closed walks, depending on whether the fundamental group of the surface is free, abelian, or hyperbolic. A key step in our algorithm for hyperbolic surfaces is the construction of a context-free grammar with O(g^2L^2) non-terminals that generates all contractible closed walks of length at most L, and only contractible closed walks, in a system of quads of genus g >= 2. Finally, we show that computing shortest simple contractible cycles, shortest simple bounding cycles, and shortest bounding closed walks are all NP-hard.
Cite as
Jeff Erickson and Yipu Wang. Topologically Trivial Closed Walks in Directed Surface Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{erickson_et_al:LIPIcs.SoCG.2019.34,
author = {Erickson, Jeff and Wang, Yipu},
title = {{Topologically Trivial Closed Walks in Directed Surface Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {34:1--34:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.34},
URN = {urn:nbn:de:0030-drops-104383},
doi = {10.4230/LIPIcs.SoCG.2019.34},
annote = {Keywords: computational topology, surface-embedded graphs, homotopy, homology, strong connectivity, hyperbolic geometry, medial axes, context-free grammars}
}
Document
Packing Disks into Disks with Optimal Worst-Case Density
Abstract
We provide a tight result for a fundamental problem arising from packing disks into a circular container: The critical density of packing disks in a disk is 0.5. This implies that any set of (not necessarily equal) disks of total area delta <= 1/2 can always be packed into a disk of area 1; on the other hand, for any epsilon>0 there are sets of disks of area 1/2+epsilon that cannot be packed. The proof uses a careful manual analysis, complemented by a minor automatic part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms.
Cite as
Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Packing Disks into Disks with Optimal Worst-Case Density. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{fekete_et_al:LIPIcs.SoCG.2019.35,
author = {Fekete, S\'{a}ndor P. and Keldenich, Phillip and Scheffer, Christian},
title = {{Packing Disks into Disks with Optimal Worst-Case Density}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {35:1--35:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.35},
URN = {urn:nbn:de:0030-drops-104398},
doi = {10.4230/LIPIcs.SoCG.2019.35},
annote = {Keywords: Disk packing, packing density, tight worst-case bound, interval arithmetic, approximation}
}
Document
Semi-Algebraic Colorings of Complete Graphs
Abstract
We consider m-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The case m = 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values of m is relevant, e.g., to problems concerning the number of distinct distances determined by a point set.
For p >= 3 and m >= 2, the classical Ramsey number R(p;m) is the smallest positive integer n such that any m-coloring of the edges of K_n, the complete graph on n vertices, contains a monochromatic K_p. It is a longstanding open problem that goes back to Schur (1916) to decide whether R(p;m)=2^{O(m)}, for a fixed p. We prove that this is true if each color class is defined semi-algebraically with bounded complexity, and that the order of magnitude of this bound is tight. Our proof is based on the Cutting Lemma of Chazelle et al., and on a Szemerédi-type regularity lemma for multicolored semi-algebraic graphs, which is of independent interest. The same technique is used to address the semi-algebraic variant of a more general Ramsey-type problem of Erdős and Shelah.
Cite as
Jacob Fox, János Pach, and Andrew Suk. Semi-Algebraic Colorings of Complete Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{fox_et_al:LIPIcs.SoCG.2019.36,
author = {Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
title = {{Semi-Algebraic Colorings of Complete Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {36:1--36:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.36},
URN = {urn:nbn:de:0030-drops-104401},
doi = {10.4230/LIPIcs.SoCG.2019.36},
annote = {Keywords: Semi-algebraic graphs, Ramsey theory, regularity lemma}
}
Document
Chunk Reduction for Multi-Parameter Persistent Homology
Abstract
The extension of persistent homology to multi-parameter setups is an algorithmic challenge. Since most computation tasks scale badly with the size of the input complex, an important pre-processing step consists of simplifying the input while maintaining the homological information. We present an algorithm that drastically reduces the size of an input. Our approach is an extension of the chunk algorithm for persistent homology (Bauer et al., Topological Methods in Data Analysis and Visualization III, 2014). We show that our construction produces the smallest multi-filtered chain complex among all the complexes quasi-isomorphic to the input, improving on the guarantees of previous work in the context of discrete Morse theory. Our algorithm also offers an immediate parallelization scheme in shared memory. Already its sequential version compares favorably with existing simplification schemes, as we show by experimental evaluation.
Cite as
Ulderico Fugacci and Michael Kerber. Chunk Reduction for Multi-Parameter Persistent Homology. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{fugacci_et_al:LIPIcs.SoCG.2019.37,
author = {Fugacci, Ulderico and Kerber, Michael},
title = {{Chunk Reduction for Multi-Parameter Persistent Homology}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {37:1--37:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.37},
URN = {urn:nbn:de:0030-drops-104413},
doi = {10.4230/LIPIcs.SoCG.2019.37},
annote = {Keywords: Multi-parameter persistent homology, Matrix reduction, Chain complexes}
}
Document
The Crossing Tverberg Theorem
Abstract
The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed.
As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.
Cite as
Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. The Crossing Tverberg Theorem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{fulek_et_al:LIPIcs.SoCG.2019.38,
author = {Fulek, Radoslav and G\"{a}rtner, Bernd and Kupavskii, Andrey and Valtr, Pavel and Wagner, Uli},
title = {{The Crossing Tverberg Theorem}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {38:1--38:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.38},
URN = {urn:nbn:de:0030-drops-104423},
doi = {10.4230/LIPIcs.SoCG.2019.38},
annote = {Keywords: Discrete geometry, Tverberg theorem, Crossing Tverberg theorem}
}
Document
Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices
Abstract
The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g.
By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Štefankovič proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus.
We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest.
Cite as
Radoslav Fulek and Jan Kynčl. Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{fulek_et_al:LIPIcs.SoCG.2019.39,
author = {Fulek, Radoslav and Kyn\v{c}l, Jan},
title = {{Z\underline2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {39:1--39:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.39},
URN = {urn:nbn:de:0030-drops-104439},
doi = {10.4230/LIPIcs.SoCG.2019.39},
annote = {Keywords: graph genus, minimum rank of a partial matrix, Hanani-Tutte theorem, graph amalgamation}
}
Document
An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting
Abstract
We study the problem of deciding if a given triple of permutations can be realized as geometric permutations of disjoint convex sets in R^3. We show that this question, which is equivalent to deciding the emptiness of certain semi-algebraic sets bounded by cubic polynomials, can be "lifted" to a purely combinatorial problem. We propose an effective algorithm for that problem, and use it to gain new insights into the structure of geometric permutations.
Cite as
Xavier Goaoc, Andreas Holmsen, and Cyril Nicaud. An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{goaoc_et_al:LIPIcs.SoCG.2019.40,
author = {Goaoc, Xavier and Holmsen, Andreas and Nicaud, Cyril},
title = {{An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {40:1--40:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.40},
URN = {urn:nbn:de:0030-drops-104442},
doi = {10.4230/LIPIcs.SoCG.2019.40},
annote = {Keywords: Geometric permutation, Emptiness testing of semi-algebraic sets, Computer-aided proof}
}
Document
Journey to the Center of the Point Set
Abstract
We revisit an algorithm of Clarkson et al. [K. L. Clarkson et al., 1996], that computes (roughly) a 1/(4d^2)-centerpoint in O~(d^9) time, for a point set in R^d, where O~ hides polylogarithmic terms. We present an improved algorithm that computes (roughly) a 1/d^2-centerpoint with running time O~(d^7). While the improvements are (arguably) mild, it is the first progress on this well known problem in over twenty years. The new algorithm is simpler, and the running time bound follows by a simple random walk argument, which we believe to be of independent interest. We also present several new applications of the improved centerpoint algorithm.
Cite as
Sariel Har-Peled and Mitchell Jones. Journey to the Center of the Point Set. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{harpeled_et_al:LIPIcs.SoCG.2019.41,
author = {Har-Peled, Sariel and Jones, Mitchell},
title = {{Journey to the Center of the Point Set}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {41:1--41:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.41},
URN = {urn:nbn:de:0030-drops-104454},
doi = {10.4230/LIPIcs.SoCG.2019.41},
annote = {Keywords: Computational geometry, Centerpoints, Random walks}
}
Document
Preprocessing Ambiguous Imprecise Points
Abstract
Let R = {R_1, R_2, ..., R_n} be a set of regions and let X = {x_1, x_2, ..., x_n} be an (unknown) point set with x_i in R_i. Region R_i represents the uncertainty region of x_i. We consider the following question: how fast can we establish order if we are allowed to preprocess the regions in R? The preprocessing model of uncertainty uses two consecutive phases: a preprocessing phase which has access only to R followed by a reconstruction phase during which a desired structure on X is computed. Recent results in this model parametrize the reconstruction time by the ply of R, which is the maximum overlap between the regions in R. We introduce the ambiguity A(R) as a more fine-grained measure of the degree of overlap in R. We show how to preprocess a set of d-dimensional disks in O(n log n) time such that we can sort X (if d=1) and reconstruct a quadtree on X (if d >= 1 but constant) in O(A(R)) time. If A(R) is sub-linear, then reporting the result dominates the running time of the reconstruction phase. However, we can still return a suitable data structure representing the result in O(A(R)) time.
In one dimension, {R} is a set of intervals and the ambiguity is linked to interval entropy, which in turn relates to the well-studied problem of sorting under partial information. The number of comparisons necessary to find the linear order underlying a poset P is lower-bounded by the graph entropy of P. We show that if P is an interval order, then the ambiguity provides a constant-factor approximation of the graph entropy. This gives a lower bound of Omega(A(R)) in all dimensions for the reconstruction phase (sorting or any proximity structure), independent of any preprocessing; hence our result is tight. Finally, our results imply that one can approximate the entropy of interval graphs in O(n log n) time, improving the O(n^{2.5}) bound by Cardinal et al.
Cite as
Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann. Preprocessing Ambiguous Imprecise Points. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 42:1-42:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{vanderhoog_et_al:LIPIcs.SoCG.2019.42,
author = {van der Hoog, Ivor and Kostitsyna, Irina and L\"{o}ffler, Maarten and Speckmann, Bettina},
title = {{Preprocessing Ambiguous Imprecise Points}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {42:1--42:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.42},
URN = {urn:nbn:de:0030-drops-104460},
doi = {10.4230/LIPIcs.SoCG.2019.42},
annote = {Keywords: preprocessing, imprecise points, entropy, sorting, proximity structures}
}
Document
Rods and Rings: Soft Subdivision Planner for R^3 x S^2
Abstract
We consider path planning for a rigid spatial robot moving amidst polyhedral obstacles. Our robot is either a rod or a ring. Being axially-symmetric, their configuration space is R^3 x S^2 with 5 degrees of freedom (DOF). Correct, complete and practical path planning for such robots is a long standing challenge in robotics. While the rod is one of the most widely studied spatial robots in path planning, the ring seems to be new, and a rare example of a non-simply-connected robot. This work provides rigorous and complete algorithms for these robots with theoretical guarantees. We implemented the algorithms in our open-source Core Library. Experiments show that they are practical, achieving near real-time performance. We compared our planner to state-of-the-art sampling planners in OMPL [Sucan et al., 2012].
Our subdivision path planner is based on the twin foundations of epsilon-exactness and soft predicates. Correct implementation is relatively easy. The technical innovations include subdivision atlases for S^2, introduction of Sigma_2 representations for footprints, and extensions of our feature-based technique for "opening up the blackbox of collision detection".
Cite as
Ching-Hsiang Hsu, Yi-Jen Chiang, and Chee Yap. Rods and Rings: Soft Subdivision Planner for R^3 x S^2. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{hsu_et_al:LIPIcs.SoCG.2019.43,
author = {Hsu, Ching-Hsiang and Chiang, Yi-Jen and Yap, Chee},
title = {{Rods and Rings: Soft Subdivision Planner for R^3 x S^2}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {43:1--43:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.43},
URN = {urn:nbn:de:0030-drops-104477},
doi = {10.4230/LIPIcs.SoCG.2019.43},
annote = {Keywords: Algorithmic Motion Planning, Subdivision Methods, Resolution-Exact Algorithms, Soft Predicates, Spatial Rod Robots, Spatial Ring Robots}
}
Document
3-Manifold Triangulations with Small Treewidth
Abstract
Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest.
First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor.
Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two.
Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.
Cite as
Kristóf Huszár and Jonathan Spreer. 3-Manifold Triangulations with Small Treewidth. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{huszar_et_al:LIPIcs.SoCG.2019.44,
author = {Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan},
title = {{3-Manifold Triangulations with Small Treewidth}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {44:1--44:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.44},
URN = {urn:nbn:de:0030-drops-104487},
doi = {10.4230/LIPIcs.SoCG.2019.44},
annote = {Keywords: computational 3-manifold topology, fixed-parameter tractability, layered triangulations, structural graph theory, treewidth, cutwidth, Heegaard genus, lens spaces, Seifert fibered spaces}
}
Document
Algorithms for Metric Learning via Contrastive Embeddings
Abstract
We study the problem of supervised learning a metric space under discriminative constraints. Given a universe X and sets S, D subset binom{X}{2} of similar and dissimilar pairs, we seek to find a mapping f:X -> Y, into some target metric space M=(Y,rho), such that similar objects are mapped to points at distance at most u, and dissimilar objects are mapped to points at distance at least l. More generally, the goal is to find a mapping of maximum accuracy (that is, fraction of correctly classified pairs). We propose approximation algorithms for various versions of this problem, for the cases of Euclidean and tree metric spaces. For both of these target spaces, we obtain fully polynomial-time approximation schemes (FPTAS) for the case of perfect information. In the presence of imperfect information we present approximation algorithms that run in quasi-polynomial time (QPTAS). We also present an exact algorithm for learning line metric spaces with perfect information in polynomial time. Our algorithms use a combination of tools from metric embeddings and graph partitioning, that could be of independent interest.
Cite as
Diego Ihara, Neshat Mohammadi, and Anastasios Sidiropoulos. Algorithms for Metric Learning via Contrastive Embeddings. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{ihara_et_al:LIPIcs.SoCG.2019.45,
author = {Ihara, Diego and Mohammadi, Neshat and Sidiropoulos, Anastasios},
title = {{Algorithms for Metric Learning via Contrastive Embeddings}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {45:1--45:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.45},
URN = {urn:nbn:de:0030-drops-104492},
doi = {10.4230/LIPIcs.SoCG.2019.45},
annote = {Keywords: metric learning, contrastive distortion, embeddings, algorithms}
}
Document
Exact Computation of the Matching Distance on 2-Parameter Persistence Modules
Abstract
The matching distance is a pseudometric on multi-parameter persistence modules, defined in terms of the weighted bottleneck distance on the restriction of the modules to affine lines. It is known that this distance is stable in a reasonable sense, and can be efficiently approximated, which makes it a promising tool for practical applications. In this work, we show that in the 2-parameter setting, the matching distance can be computed exactly in polynomial time. Our approach subdivides the space of affine lines into regions, via a line arrangement. In each region, the matching distance restricts to a simple analytic function, whose maximum is easily computed. As a byproduct, our analysis establishes that the matching distance is a rational number, if the bigrades of the input modules are rational.
Cite as
Michael Kerber, Michael Lesnick, and Steve Oudot. Exact Computation of the Matching Distance on 2-Parameter Persistence Modules. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{kerber_et_al:LIPIcs.SoCG.2019.46,
author = {Kerber, Michael and Lesnick, Michael and Oudot, Steve},
title = {{Exact Computation of the Matching Distance on 2-Parameter Persistence Modules}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {46:1--46:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.46},
URN = {urn:nbn:de:0030-drops-104505},
doi = {10.4230/LIPIcs.SoCG.2019.46},
annote = {Keywords: Topological Data Analysis, Multi-Parameter Persistence, Line arrangements}
}
Document
Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling
Abstract
We study a variant of the median problem for a collection of point sets in high dimensions. This generalizes the geometric median as well as the (probabilistic) smallest enclosing ball (pSEB) problems. Our main objective and motivation is to improve the previously best algorithm for the pSEB problem by reducing its exponential dependence on the dimension to linear. This is achieved via a novel combination of sampling techniques for clustering problems in metric spaces with the framework of stochastic subgradient descent. As a result, the algorithm becomes applicable to shape fitting problems in Hilbert spaces of unbounded dimension via kernel functions. We present an exemplary application by extending the support vector data description (SVDD) shape fitting method to the probabilistic case. This is done by simulating the pSEB algorithm implicitly in the feature space induced by the kernel function.
Cite as
Amer Krivošija and Alexander Munteanu. Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{krivosija_et_al:LIPIcs.SoCG.2019.47,
author = {Krivo\v{s}ija, Amer and Munteanu, Alexander},
title = {{Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {47:1--47:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.47},
URN = {urn:nbn:de:0030-drops-104515},
doi = {10.4230/LIPIcs.SoCG.2019.47},
annote = {Keywords: geometric median, convex optimization, smallest enclosing ball, probabilistic data, support vector data description, kernel methods}
}
Document
A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
Abstract
We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(A cup B,E) with edge weights of 0 or 1. Let w <= n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in O~(m(sqrt{w} + sqrt{r} + wr/n)) time.
When all the edge weights are 1 (symmetrically when all weights are 0), our algorithm will be identical to the well-known Hopcroft-Karp (HK) algorithm, which runs in O(m sqrt{n}) time. However, if we can carefully assign weights of 0 and 1 on its edges such that both w and r are sub-linear in n and wr=O(n^{gamma}) for gamma < 3/2, then we can compute maximum cardinality matching in G in o(m sqrt{n}) time. Using our algorithm, we obtain a new O~(n^{4/3}/epsilon^4) time algorithm to compute an epsilon-approximate bottleneck matching of A,B subsetR^2 and an 1/(epsilon^{O(d)}}n^{1+(d-1)/(2d-1)}) poly log n time algorithm for computing epsilon-approximate bottleneck matching in d-dimensions. All previous algorithms take Omega(n^{3/2}) time. Given any graph G(A cup B,E) that has an easily computable balanced vertex separator for every subgraph G'(V',E') of size |V'|^{delta}, for delta in [1/2,1), we can apply our algorithm to compute a maximum matching in O~(mn^{delta/1+delta}) time improving upon the O(m sqrt{n}) time taken by the HK-Algorithm.
Cite as
Nathaniel Lahn and Sharath Raghvendra. A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{lahn_et_al:LIPIcs.SoCG.2019.48,
author = {Lahn, Nathaniel and Raghvendra, Sharath},
title = {{A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {48:1--48:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.48},
URN = {urn:nbn:de:0030-drops-104528},
doi = {10.4230/LIPIcs.SoCG.2019.48},
annote = {Keywords: Bipartite matching, Bottleneck matching}
}
Document
The Unbearable Hardness of Unknotting
Abstract
We prove that deciding if a diagram of the unknot can be untangled using at most k Reidemeister moves (where k is part of the input) is NP-hard. We also prove that several natural questions regarding links in the 3-sphere are NP-hard, including detecting whether a link contains a trivial sublink with n components, computing the unlinking number of a link, and computing a variety of link invariants related to four-dimensional topology (such as the 4-ball Euler characteristic, the slicing number, and the 4-dimensional clasp number).
Cite as
Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, and Martin Tancer. The Unbearable Hardness of Unknotting. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{demesmay_et_al:LIPIcs.SoCG.2019.49,
author = {de Mesmay, Arnaud and Rieck, Yo'av and Sedgwick, Eric and Tancer, Martin},
title = {{The Unbearable Hardness of Unknotting}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {49:1--49:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.49},
URN = {urn:nbn:de:0030-drops-104530},
doi = {10.4230/LIPIcs.SoCG.2019.49},
annote = {Keywords: Knot, Link, NP-hard, Reidemeister move, Unknot recognition, Unlinking number, intermediate invariants}
}
Document
On Grids in Point-Line Arrangements in the Plane
Abstract
The famous Szemerédi-Trotter theorem states that any arrangement of n points and n lines in the plane determines O(n^{4/3}) incidences, and this bound is tight. In this paper, we prove the following Turán-type result for point-line incidence. Let L_a and L_b be two sets of t lines in the plane and let P={l_a cap l_b : l_a in L_a, l_b in L_b} be the set of intersection points between L_a and L_b. We say that (P, L_a cup L_b) forms a natural t x t grid if |P| =t^2, and conv(P) does not contain the intersection point of some two lines in L_a and does not contain the intersection point of some two lines in L_b. For fixed t > 1, we show that any arrangement of n points and n lines in the plane that does not contain a natural t x t grid determines O(n^{4/3- epsilon}) incidences, where epsilon = epsilon(t)>0. We also provide a construction of n points and n lines in the plane that does not contain a natural 2 x 2 grid and determines at least Omega(n^{1+1/14}) incidences.
Cite as
Mozhgan Mirzaei and Andrew Suk. On Grids in Point-Line Arrangements in the Plane. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 50:1-50:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{mirzaei_et_al:LIPIcs.SoCG.2019.50,
author = {Mirzaei, Mozhgan and Suk, Andrew},
title = {{On Grids in Point-Line Arrangements in the Plane}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {50:1--50:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.50},
URN = {urn:nbn:de:0030-drops-104541},
doi = {10.4230/LIPIcs.SoCG.2019.50},
annote = {Keywords: Szemer\'{e}di-Trotter Theorem, Grids, Sidon sets}
}
Document
On Weak epsilon-Nets and the Radon Number
Abstract
We show that the Radon number characterizes the existence of weak nets in separable convexity spaces (an abstraction of the Euclidean notion of convexity). The construction of weak nets when the Radon number is finite is based on Helly’s property and on metric properties of VC classes. The lower bound on the size of weak nets when the Radon number is large relies on the chromatic number of the Kneser graph. As an application, we prove an amplification result for weak epsilon-nets.
Cite as
Shay Moran and Amir Yehudayoff. On Weak epsilon-Nets and the Radon Number. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{moran_et_al:LIPIcs.SoCG.2019.51,
author = {Moran, Shay and Yehudayoff, Amir},
title = {{On Weak epsilon-Nets and the Radon Number}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {51:1--51:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.51},
URN = {urn:nbn:de:0030-drops-104551},
doi = {10.4230/LIPIcs.SoCG.2019.51},
annote = {Keywords: abstract convexity, weak epsilon nets, Radon number, VC dimension, Haussler packing lemma, Kneser graphs}
}
Document
Dynamic Planar Point Location in External Memory
Abstract
In this paper we describe a fully-dynamic data structure for the planar point location problem in the external memory model. Our data structure supports queries in O(log_B n(log log_B n)^3)) I/Os and updates in O(log_B n(log log_B n)^2)) amortized I/Os, where n is the number of segments in the subdivision and B is the block size. This is the first dynamic data structure with almost-optimal query cost. For comparison all previously known results for this problem require O(log_B^2 n) I/Os to answer queries. Our result almost matches the best known upper bound in the internal-memory model.
Cite as
J. Ian Munro and Yakov Nekrich. Dynamic Planar Point Location in External Memory. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{munro_et_al:LIPIcs.SoCG.2019.52,
author = {Munro, J. Ian and Nekrich, Yakov},
title = {{Dynamic Planar Point Location in External Memory}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {52:1--52:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.52},
URN = {urn:nbn:de:0030-drops-104566},
doi = {10.4230/LIPIcs.SoCG.2019.52},
annote = {Keywords: Data Structures, Dynamic Data Structures, Planar Point Location, External Memory}
}
Document
Efficient Algorithms for Ortho-Radial Graph Drawing
Abstract
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths.
Barth et al. [2017] have established the existence of an analogous ortho-radial representation for ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of the ortho-radial grid that makes the problem of characterizing valid ortho-radial representations all the more complex and interesting. Barth et al. prove such a characterization. However, the proof is existential and does not provide an efficient algorithm for testing whether a given ortho-radial representation is valid, let alone actually obtaining a drawing from an ortho-radial representation.
In this paper we give quadratic-time algorithms for both of these tasks. They are based on a suitably constrained left-first DFS in planar graphs and several new insights on ortho-radial representations. Our validity check requires quadratic time, and a naive application of it would yield a quartic algorithm for constructing a drawing from a valid ortho-radial representation. Using further structural insights we speed up the drawing algorithm to quadratic running time.
Cite as
Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Efficient Algorithms for Ortho-Radial Graph Drawing. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{niedermann_et_al:LIPIcs.SoCG.2019.53,
author = {Niedermann, Benjamin and Rutter, Ignaz and Wolf, Matthias},
title = {{Efficient Algorithms for Ortho-Radial Graph Drawing}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {53:1--53:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.53},
URN = {urn:nbn:de:0030-drops-104572},
doi = {10.4230/LIPIcs.SoCG.2019.53},
annote = {Keywords: Graph Drawing, Ortho-Radial Graph Drawing, Ortho-Radial Representation, Topology-Shape-Metrics, Efficient Algorithms}
}
Document
On the Chromatic Number of Disjointness Graphs of Curves
Abstract
Let omega(G) and chi(G) denote the clique number and chromatic number of a graph G, respectively. The disjointness graph of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called x-monotone if every vertical line intersects it in at most one point. An x-monotone curve is grounded if its left endpoint lies on the y-axis.
We prove that if G is the disjointness graph of a family of grounded x-monotone curves such that omega(G)=k, then chi(G)<= binom{k+1}{2}. If we only require that every curve is x-monotone and intersects the y-axis, then we have chi(G)<= k+1/2 binom{k+2}{3}. Both of these bounds are best possible. The construction showing the tightness of the last result settles a 25 years old problem: it yields that there exist K_k-free disjointness graphs of x-monotone curves such that any proper coloring of them uses at least Omega(k^{4}) colors. This matches the upper bound up to a constant factor.
Cite as
János Pach and István Tomon. On the Chromatic Number of Disjointness Graphs of Curves. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{pach_et_al:LIPIcs.SoCG.2019.54,
author = {Pach, J\'{a}nos and Tomon, Istv\'{a}n},
title = {{On the Chromatic Number of Disjointness Graphs of Curves}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {54:1--54:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.54},
URN = {urn:nbn:de:0030-drops-104582},
doi = {10.4230/LIPIcs.SoCG.2019.54},
annote = {Keywords: string graph, chromatic number, intersection graph}
}
Document
Computing Persistent Homology of Flag Complexes via Strong Collapses
Abstract
In this article, we focus on the problem of computing Persistent Homology of a flag tower, i.e. a sequence of flag complexes connected by simplicial maps. We show that if we restrict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. We show that strong collapses of flag complexes can be computed in time O(k^2v^2) where v is the number of vertices of the complex and k is the maximal degree of its graph. Moreover we can strong collapse a flag complex knowing only its 1-skeleton and the resulting complex is also a flag complex. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient.
Cite as
Jean-Daniel Boissonnat and Siddharth Pritam. Computing Persistent Homology of Flag Complexes via Strong Collapses. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2019.55,
author = {Boissonnat, Jean-Daniel and Pritam, Siddharth},
title = {{Computing Persistent Homology of Flag Complexes via Strong Collapses}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {55:1--55:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.55},
URN = {urn:nbn:de:0030-drops-104596},
doi = {10.4230/LIPIcs.SoCG.2019.55},
annote = {Keywords: Computational Topology, Topological Data Analysis, Strong Collapse, Persistent homology}
}
Document
Ham-Sandwich Cuts and Center Transversals in Subspaces
Abstract
The Ham-Sandwich theorem is a well-known result in geometry. It states that any d mass distributions in R^d can be simultaneously bisected by a hyperplane. The result is tight, that is, there are examples of d+1 mass distributions that cannot be simultaneously bisected by a single hyperplane. In this abstract we will study the following question: given a continuous assignment of mass distributions to certain subsets of R^d, is there a subset on which we can bisect more masses than what is guaranteed by the Ham-Sandwich theorem?
We investigate two types of subsets. The first type are linear subspaces of R^d, i.e., k-dimensional flats containing the origin. We show that for any continuous assignment of d mass distributions to the k-dimensional linear subspaces of R^d, there is always a subspace on which we can simultaneously bisect the images of all d assignments. We extend this result to center transversals, a generalization of Ham-Sandwich cuts. As for Ham-Sandwich cuts, we further show that for d-k+2 masses, we can choose k-1 of the vectors defining the k-dimensional subspace in which the solution lies.
The second type of subsets we consider are subsets that are determined by families of n hyperplanes in R^d. Also in this case, we find a Ham-Sandwich-type result. In an attempt to solve a conjecture by Langerman about bisections with several cuts, we show that our underlying topological result can be used to prove this conjecture in a relaxed setting.
Cite as
Patrick Schnider. Ham-Sandwich Cuts and Center Transversals in Subspaces. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{schnider:LIPIcs.SoCG.2019.56,
author = {Schnider, Patrick},
title = {{Ham-Sandwich Cuts and Center Transversals in Subspaces}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {56:1--56:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.56},
URN = {urn:nbn:de:0030-drops-104609},
doi = {10.4230/LIPIcs.SoCG.2019.56},
annote = {Keywords: Ham-Sandwich cuts, center transversal, topological methods}
}
Document
Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges
Abstract
A family R of ranges and a set X of points, all in R^d, together define a range space (X, R|_X), where R|_X = {X cap h | h in R}. We want to find a structure to estimate the quantity |X cap h|/|X| for any range h in R with the (rho, epsilon)-guarantee: (i) if |X cap h|/|X| > rho, the estimate must have a relative error epsilon; (ii) otherwise, the estimate must have an absolute error rho epsilon. The objective is to minimize the size of the structure. Currently, the dominant solution is to compute a relative (rho, epsilon)-approximation, which is a subset of X with O~(lambda/(rho epsilon^2)) points, where lambda is the VC-dimension of (X, R|_X), and O~ hides polylog factors.
This paper shows a more general bound sensitive to the content of X. We give a structure that stores O(log (1/rho)) integers plus O~(theta * (lambda/epsilon^2)) points of X, where theta - called the disagreement coefficient - measures how much the ranges differ from each other in their intersections with X. The value of theta is between 1 and 1/rho, such that our space bound is never worse than that of relative (rho, epsilon)-approximations, but we improve the latter’s 1/rho term whenever theta = o(1/(rho log (1/rho))). We also prove that, in the worst case, summaries with the (rho, 1/2)-guarantee must consume Omega(theta) words even for d = 2 and lambda <=3.
We then constrain R to be the set of halfspaces in R^d for a constant d, and prove the existence of structures with o(1/(rho epsilon^2)) size offering (rho,epsilon)-guarantees, when X is generated from various stochastic distributions. This is the first formal justification on why the term 1/rho is not compulsory for "realistic" inputs.
Cite as
Yufei Tao and Yu Wang. Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{tao_et_al:LIPIcs.SoCG.2019.57,
author = {Tao, Yufei and Wang, Yu},
title = {{Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {57:1--57:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.57},
URN = {urn:nbn:de:0030-drops-104617},
doi = {10.4230/LIPIcs.SoCG.2019.57},
annote = {Keywords: Relative Approximation, Disagreement Coefficient, Data Summary}
}
Document
DTM-Based Filtrations
Abstract
Despite strong stability properties, the persistent homology of filtrations classically used in Topological Data Analysis, such as, e.g. the Čech or Vietoris-Rips filtrations, are very sensitive to the presence of outliers in the data from which they are computed. In this paper, we introduce and study a new family of filtrations, the DTM-filtrations, built on top of point clouds in the Euclidean space which are more robust to noise and outliers. The approach adopted in this work relies on the notion of distance-to-measure functions and extends some previous work on the approximation of such functions.
Cite as
Hirokazu Anai, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hiroya Inakoshi, Raphaël Tinarrage, and Yuhei Umeda. DTM-Based Filtrations. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{anai_et_al:LIPIcs.SoCG.2019.58,
author = {Anai, Hirokazu and Chazal, Fr\'{e}d\'{e}ric and Glisse, Marc and Ike, Yuichi and Inakoshi, Hiroya and Tinarrage, Rapha\"{e}l and Umeda, Yuhei},
title = {{DTM-Based Filtrations}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {58:1--58:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.58},
URN = {urn:nbn:de:0030-drops-104623},
doi = {10.4230/LIPIcs.SoCG.2019.58},
annote = {Keywords: Topological Data Analysis, Persistent homology}
}
Document
A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains
Abstract
Let P be a polygonal domain of h holes and n vertices. We study the problem of constructing a data structure that can compute a shortest path between s and t in P under the L_1 metric for any two query points s and t. To do so, a standard approach is to first find a set of n_s "gateways" for s and a set of n_t "gateways" for t such that there exist a shortest s-t path containing a gateway of s and a gateway of t, and then compute a shortest s-t path using these gateways. Previous algorithms all take quadratic O(n_s * n_t) time to solve this problem. In this paper, we propose a divide-and-conquer technique that solves the problem in O(n_s + n_t log n_s) time. As a consequence, we construct a data structure of O(n+(h^2 log^3 h/log log h)) size in O(n+(h^2 log^4 h/log log h)) time such that each query can be answered in O(log n) time.
Cite as
Haitao Wang. A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{wang:LIPIcs.SoCG.2019.59,
author = {Wang, Haitao},
title = {{A Divide-and-Conquer Algorithm for Two-Point L\underline1 Shortest Path Queries in Polygonal Domains}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {59:1--59:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.59},
URN = {urn:nbn:de:0030-drops-104631},
doi = {10.4230/LIPIcs.SoCG.2019.59},
annote = {Keywords: shortest paths, two-point queries, L\underline1 metric, polygonal domains}
}
Document
Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs
Abstract
We revisit a classical graph-theoretic problem, the single-source shortest-path (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic) algorithm which solves the problem in O(n log^2 n) time using linear space, where n is the number of the vertices of the graph. This significantly improves the previous deterministic algorithm by Cabello and Jejčič [CGTA'15] which uses O(n^{1+delta}) time and O(n^{1+delta}) space (for any small constant delta>0) and the previous randomized algorithm by Kaplan et al. [SODA'17] which uses O(n log^{12+o(1)} n) expected time and O(n log^3 n) space. More specifically, we show that if the 2D offline insertion-only (additively-)weighted nearest-neighbor problem with k operations (i.e., insertions and queries) can be solved in f(k) time, then the SSSP problem in weighted unit-disk graphs can be solved in O(n log n+f(n)) time. Using the same framework with some new ideas, we also obtain a (1+epsilon)-approximate algorithm for the problem, using O(n log n + n log^2(1/epsilon)) time and linear space. This improves the previous (1+epsilon)-approximate algorithm by Chan and Skrepetos [SoCG'18] which uses O((1/epsilon)^2 n log n) time and O((1/epsilon)^2 n) space. Because of the Omega(n log n)-time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal.
Cite as
Haitao Wang and Jie Xue. Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 60:1-60:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{wang_et_al:LIPIcs.SoCG.2019.60,
author = {Wang, Haitao and Xue, Jie},
title = {{Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {60:1--60:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.60},
URN = {urn:nbn:de:0030-drops-104649},
doi = {10.4230/LIPIcs.SoCG.2019.60},
annote = {Keywords: Single-source shortest paths, Weighted unit-disk graphs, Geometric graph algorithms}
}
Document
Searching for the Closest-Pair in a Query Translate
Abstract
We consider a range-search variant of the closest-pair problem. Let Gamma be a fixed shape in the plane. We are interested in storing a given set of n points in the plane in some data structure such that for any specified translate of Gamma, the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important settings: when Gamma is a polygon (possibly with holes) and when Gamma is a general convex body whose boundary is smooth. When Gamma is a polygon, we present a data structure using O(n) space and O(log n) query time, which is asymptotically optimal. When Gamma is a general convex body with a smooth boundary, we give a near-optimal data structure using O(n log n) space and O(log^2 n) query time. Our results settle some open questions posed by Xue et al. at SoCG 2018.
Cite as
Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan. Searching for the Closest-Pair in a Query Translate. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{xue_et_al:LIPIcs.SoCG.2019.61,
author = {Xue, Jie and Li, Yuan and Rahul, Saladi and Janardan, Ravi},
title = {{Searching for the Closest-Pair in a Query Translate}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {61:1--61:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.61},
URN = {urn:nbn:de:0030-drops-104659},
doi = {10.4230/LIPIcs.SoCG.2019.61},
annote = {Keywords: Closest pair, Range search, Geometric data structures, Translation query}
}
Document
On the Complexity of the k-Level in Arrangements of Pseudoplanes
Abstract
A classical open problem in combinatorial geometry is to obtain tight asymptotic bounds on the maximum number of k-level vertices in an arrangement of n hyperplanes in R^d (vertices with exactly k of the hyperplanes passing below them). This is essentially a dual version of the k-set problem, which, in a primal setting, seeks bounds for the maximum number of k-sets determined by n points in R^d, where a k-set is a subset of size k that can be separated from its complement by a hyperplane. The k-set problem is still wide open even in the plane. In three dimensions, the best known upper and lower bounds are, respectively, O(nk^{3/2}) [M. Sharir et al., 2001] and nk * 2^{Omega(sqrt{log k})} [G. Tóth, 2000].
In its dual version, the problem can be generalized by replacing hyperplanes by other families of surfaces (or curves in the planes). Reasonably sharp bounds have been obtained for curves in the plane [M. Sharir and J. Zahl, 2017; H. Tamaki and T. Tokuyama, 2003], but the known upper bounds are rather weak for more general surfaces, already in three dimensions, except for the case of triangles [P. K. Agarwal et al., 1998]. The best known general bound, due to Chan [T. M. Chan, 2012] is O(n^{2.997}), for families of surfaces that satisfy certain (fairly weak) properties.
In this paper we consider the case of pseudoplanes in R^3 (defined in detail in the introduction), and establish the upper bound O(nk^{5/3}) for the number of k-level vertices in an arrangement of n pseudoplanes. The bound is obtained by establishing suitable (and nontrivial) extensions of dual versions of classical tools that have been used in studying the primal k-set problem, such as the Lovász Lemma and the Crossing Lemma.
Cite as
Micha Sharir and Chen Ziv. On the Complexity of the k-Level in Arrangements of Pseudoplanes. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{sharir_et_al:LIPIcs.SoCG.2019.62,
author = {Sharir, Micha and Ziv, Chen},
title = {{On the Complexity of the k-Level in Arrangements of Pseudoplanes}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {62:1--62:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.62},
URN = {urn:nbn:de:0030-drops-104662},
doi = {10.4230/LIPIcs.SoCG.2019.62},
annote = {Keywords: k-level, pseudoplanes, arrangements, three dimensions, k-sets}
}
Document
Multimedia Exposition
Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition)
Abstract
We motivate and visualize problems and methods for packing a set of objects into a given container, in particular a set of {different-size} circles or squares into a square or circular container. Questions of this type have attracted a considerable amount of attention and are known to be notoriously hard. We focus on a particularly simple criterion for deciding whether a set can be packed: comparing the total area A of all objects to the area C of the container. The critical packing density delta^* is the largest value A/C for which any set of area A can be packed into a container of area C. We describe algorithms that establish the critical density of squares in a square (delta^*=0.5), of circles in a square (delta^*=0.5390 ...), regular octagons in a square (delta^*=0.5685 ...), and circles in a circle (delta^*=0.5).
Cite as
Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Sebastian Morr, and Christian Scheffer. Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 63:1-63:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{becker_et_al:LIPIcs.SoCG.2019.63,
author = {Becker, Aaron T. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Morr, Sebastian and Scheffer, Christian},
title = {{Packing Geometric Objects with Optimal Worst-Case Density}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {63:1--63:6},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.63},
URN = {urn:nbn:de:0030-drops-104678},
doi = {10.4230/LIPIcs.SoCG.2019.63},
annote = {Keywords: Packing, complexity, bounds, packing density}
}
Document
Multimedia Exposition
Properties of Minimal-Perimeter Polyominoes (Multimedia Exposition)
Abstract
In this video, we survey some results concerning polyominoes, which are sets of connected cells on the square lattice, and specifically, minimal-perimeter polyominoes, that are polyominoes with the minimal-perimeter from all polyominoes of the same size.
Cite as
Gill Barequet and Gil Ben-Shachar. Properties of Minimal-Perimeter Polyominoes (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 64:1-64:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{barequet_et_al:LIPIcs.SoCG.2019.64,
author = {Barequet, Gill and Ben-Shachar, Gil},
title = {{Properties of Minimal-Perimeter Polyominoes}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {64:1--64:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.64},
URN = {urn:nbn:de:0030-drops-104687},
doi = {10.4230/LIPIcs.SoCG.2019.64},
annote = {Keywords: Polyominoes, Perimeter, Minimal-Perimeter}
}
Document
Multimedia Exposition
A Manual Comparison of Convex Hull Algorithms (Multimedia Exposition)
Abstract
We have verified experimentally that there is at least one point set on which Andrew’s algorithm (based on Graham’s scan) to compute the convex hull of a set of points in the plane is significantly faster than a brute-force approach, thus supporting existing theoretical analysis with practical evidence. Specifically, we determined that executing Andrew’s algorithm on the point set P = {(1,4), (2,8), (3,10), (4,1), (5,7), (6,3), (7,9), (8,5), (9,2), (10,6)} takes 41 minutes and 18 seconds; the brute-force approach takes 3 hours, 49 minutes, and 5 seconds.
Cite as
Maarten Löffler. A Manual Comparison of Convex Hull Algorithms (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 65:1-65:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{loffler:LIPIcs.SoCG.2019.65,
author = {L\"{o}ffler, Maarten},
title = {{A Manual Comparison of Convex Hull Algorithms}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {65:1--65:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.65},
URN = {urn:nbn:de:0030-drops-104690},
doi = {10.4230/LIPIcs.SoCG.2019.65},
annote = {Keywords: convex hull, efficiency}
}
Document
Multimedia Exposition
Fréchet View - A Tool for Exploring Fréchet Distance Algorithms (Multimedia Exposition)
Abstract
The Fréchet-distance is a similarity measure for geometric shapes. Alt and Godau presented the first algorithm for computing the Fréchet-distance and introduced a key concept, the free-space diagram. Since then, numerous variants of the Fréchet-distance have been studied.
We present here an interactive, graphical tool for exploring some Fréchet-distance algorithms. Given two curves, users can experiment with the free-space diagram and compute the Fréchet-distance. The Fréchet-distance can be computed for two important classes of shapes: for polygonal curves in the plane, and for simple polygonal surfaces.
Finally, we demonstrate an implementation of a very recent concept, the k-Fréchet-distance.
Cite as
Peter Schäfer. Fréchet View - A Tool for Exploring Fréchet Distance Algorithms (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 66:1-66:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{schafer:LIPIcs.SoCG.2019.66,
author = {Sch\"{a}fer, Peter},
title = {{Fr\'{e}chet View - A Tool for Exploring Fr\'{e}chet Distance Algorithms}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {66:1--66:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Barequet, Gill and Wang, Yusu},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.66},
URN = {urn:nbn:de:0030-drops-104703},
doi = {10.4230/LIPIcs.SoCG.2019.66},
annote = {Keywords: Fr\'{e}chet distance, free-space diagram, polygonal curves, simple polygons}
}