Volume
LIPIcs, Volume 99
34th International Symposium on Computational Geometry (SoCG 2018)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG)
Event
SoCG 2018, June 11-14, 2018, Budapest, HungaryEditors
Publication Details
- published at: 2018-06-08
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-066-8
- DBLP: db/conf/compgeom/compgeom2017
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 99, SoCG'18, Complete Volume
Abstract
LIPIcs, Volume 99, SoCG'18, Complete Volume
Cite as
34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@Proceedings{speckmann_et_al:LIPIcs.SoCG.2018,
title = {{LIPIcs, Volume 99, SoCG'18, Complete Volume}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018},
URN = {urn:nbn:de:0030-drops-89308},
doi = {10.4230/LIPIcs.SoCG.2018},
annote = {Keywords: Theory of computation, Computational geometry, Mathematics of computing, Combinatorics, Theory of computation, Design and analysis of algorithms}
}
Document
Front Matter
Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks
Abstract
Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks
Cite as
34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 0:i-0:xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{speckmann_et_al:LIPIcs.SoCG.2018.0,
author = {Speckmann, Bettina and T\'{o}th, Csaba D.},
title = {{Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {0:i--0:xi},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.0},
URN = {urn:nbn:de:0030-drops-87136},
doi = {10.4230/LIPIcs.SoCG.2018.0},
annote = {Keywords: Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks}
}
Document
Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm
Abstract
We study the problem of decomposing a volume bounded by a smooth surface into a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay meshing, a principled solution to this problem for generic smooth surfaces remained elusive. VoroCrust leverages ideas from alpha-shapes and the power crust algorithm to produce unweighted Voronoi cells conforming to the surface, yielding the first provably-correct algorithm for this problem. Given an epsilon-sample on the bounding surface, with a weak sigma-sparsity condition, we work with the balls of radius delta times the local feature size centered at each sample. The corners of this union of balls are the Voronoi sites, on both sides of the surface. The facets common to cells on opposite sides reconstruct the surface. For appropriate values of epsilon, sigma and delta, we prove that the surface reconstruction is isotopic to the bounding surface. With the surface protected, the enclosed volume can be further decomposed into an isotopic volume mesh of fat Voronoi cells by generating a bounded number of sites in its interior. Compared to state-of-the-art methods based on clipping, VoroCrust cells are full Voronoi cells, with convexity and fatness guarantees. Compared to the power crust algorithm, VoroCrust cells are not filtered, are unweighted, and offer greater flexibility in meshing the enclosed volume by either structured grids or random samples.
Cite as
Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, and Ahmad A. Rushdi. Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{abdelkader_et_al:LIPIcs.SoCG.2018.1,
author = {Abdelkader, Ahmed and Bajaj, Chandrajit L. and Ebeida, Mohamed S. and Mahmoud, Ahmed H. and Mitchell, Scott A. and Owens, John D. and Rushdi, Ahmad A.},
title = {{Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {1:1--1:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.1},
URN = {urn:nbn:de:0030-drops-87147},
doi = {10.4230/LIPIcs.SoCG.2018.1},
annote = {Keywords: sampling conditions, surface reconstruction, polyhedral meshing, Voronoi}
}
Document
Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs
Abstract
We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0.
In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.
Cite as
A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, and Shakhar Smorodinsky. Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{abuaffash_et_al:LIPIcs.SoCG.2018.2,
author = {Abu-Affash, A. Karim and Carmi, Paz and Maheshwari, Anil and Morin, Pat and Smid, Michiel and Smorodinsky, Shakhar},
title = {{Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {2:1--2:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.2},
URN = {urn:nbn:de:0030-drops-87152},
doi = {10.4230/LIPIcs.SoCG.2018.2},
annote = {Keywords: Approximation algorithms, maximum diameter-bounded subgraph, unit disk graphs, fractional Helly theorem, VC-dimension}
}
Document
Vietoris-Rips and Cech Complexes of Metric Gluings
Abstract
We study Vietoris-Rips and Cech complexes of metric wedge sums and metric gluings. We show that the Vietoris-Rips (resp. Cech) complex of a wedge sum, equipped with a natural metric, is homotopy equivalent to the wedge sum of the Vietoris-Rips (resp. Cech) complexes. We also provide generalizations for certain metric gluings, i.e. when two metric spaces are glued together along a common isometric subset. As our main example, we deduce the homotopy type of the Vietoris-Rips complex of two metric graphs glued together along a sufficiently short path. As a result, we can describe the persistent homology, in all homological dimensions, of the Vietoris-Rips complexes of a wide class of metric graphs.
Cite as
Michal Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier. Vietoris-Rips and Cech Complexes of Metric Gluings. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{adamaszek_et_al:LIPIcs.SoCG.2018.3,
author = {Adamaszek, Michal and Adams, Henry and Gasparovic, Ellen and Gommel, Maria and Purvine, Emilie and Sazdanovic, Radmila and Wang, Bei and Wang, Yusu and Ziegelmeier, Lori},
title = {{Vietoris-Rips and Cech Complexes of Metric Gluings}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {3:1--3:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.3},
URN = {urn:nbn:de:0030-drops-87162},
doi = {10.4230/LIPIcs.SoCG.2018.3},
annote = {Keywords: Vietoris-Rips and Cech complexes, metric space gluings and wedge sums, metric graphs, persistent homology}
}
Document
Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon
Abstract
We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set S of point sites in a static simple polygon P. Our data structure allows us to insert a new site in S, delete a site from S, and ask for the site in S closest to an arbitrary query point q in P. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in P. Our data structure achieves polylogarithmic update and query times, and uses O(n log^3n log m + m) space, where n is the number of sites in S and m is the number of vertices in P. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently.
Cite as
Pankaj K. Agarwal, Lars Arge, and Frank Staals. Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2018.4,
author = {Agarwal, Pankaj K. and Arge, Lars and Staals, Frank},
title = {{Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {4:1--4:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.4},
URN = {urn:nbn:de:0030-drops-87175},
doi = {10.4230/LIPIcs.SoCG.2018.4},
annote = {Keywords: data structure, simple polygon, geodesic distance, nearest neighbor searching, shallow cutting}
}
Document
O~(n^{1/3})-Space Algorithm for the Grid Graph Reachability Problem
Abstract
The directed graph reachability problem takes as input an n-vertex directed graph G=(V,E), and two distinguished vertices s and t. The problem is to determine whether there exists a path from s to t in G. This is a canonical complete problem for class NL. Asano et al. proposed an O~(sqrt{n}) space and polynomial time algorithm for the directed grid and planar graph reachability problem. The main result of this paper is to show that the directed graph reachability problem restricted to grid graphs can be solved in polynomial time using only O~(n^{1/3}) space.
Cite as
Ryo Ashida and Kotaro Nakagawa. O~(n^{1/3})-Space Algorithm for the Grid Graph Reachability Problem. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{ashida_et_al:LIPIcs.SoCG.2018.5,
author = {Ashida, Ryo and Nakagawa, Kotaro},
title = {{O\textasciitilde(n^\{1/3\})-Space Algorithm for the Grid Graph Reachability Problem}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {5:1--5:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.5},
URN = {urn:nbn:de:0030-drops-87182},
doi = {10.4230/LIPIcs.SoCG.2018.5},
annote = {Keywords: graph reachability, grid graph, graph algorithm, sublinear space algorithm}
}
Document
The Reverse Kakeya Problem
Abstract
We prove a generalization of Pál's 1921 conjecture that if a convex shape P can be placed in any orientation inside a convex shape Q in the plane, then P can also be turned continuously through 360° inside Q. We also prove a lower bound of Omega(m n^{2}) on the number of combinatorially distinct maximal placements of a convex m-gon P in a convex n-gon Q. This matches the upper bound proven by Agarwal et al.
Cite as
Sang Won Bae, Sergio Cabello, Otfried Cheong, Yoonsung Choi, Fabian Stehn, and Sang Duk Yoon. The Reverse Kakeya Problem. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bae_et_al:LIPIcs.SoCG.2018.6,
author = {Bae, Sang Won and Cabello, Sergio and Cheong, Otfried and Choi, Yoonsung and Stehn, Fabian and Yoon, Sang Duk},
title = {{The Reverse Kakeya Problem}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {6:1--6:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.6},
URN = {urn:nbn:de:0030-drops-87199},
doi = {10.4230/LIPIcs.SoCG.2018.6},
annote = {Keywords: Kakeya problem, convex, isodynamic point, turning}
}
Document
Capacitated Covering Problems in Geometric Spaces
Abstract
In this article, we consider the following capacitated covering problem. We are given a set P of n points and a set B of balls from some metric space, and a positive integer U that represents the capacity of each of the balls in B. We would like to compute a subset B' subseteq B of balls and assign each point in P to some ball in B' that contains it, such that the number of points assigned to any ball is at most U. The objective function that we would like to minimize is the cardinality of B'.
We consider this problem in arbitrary metric spaces as well as Euclidean spaces of constant dimension. In the metric setting, even the uncapacitated version of the problem is hard to approximate to within a logarithmic factor. In the Euclidean setting, the best known approximation guarantee in dimensions 3 and higher is logarithmic in the number of points. Thus we focus on obtaining "bi-criteria" approximations. In particular, we are allowed to expand the balls in our solution by some factor, but optimal solutions do not have that flexibility. Our main result is that allowing constant factor expansion of the input balls suffices to obtain constant approximations for this problem. In fact, in the Euclidean setting, only (1+epsilon) factor expansion is sufficient for any epsilon > 0, with the approximation factor being a polynomial in 1/epsilon. We obtain these results using a unified scheme for rounding the natural LP relaxation; this scheme may be useful for other capacitated covering problems. We also complement these bi-criteria approximations by obtaining hardness of approximation results that shed light on our understanding of these problems.
Cite as
Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar, and Kasturi Varadarajan. Capacitated Covering Problems in Geometric Spaces. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2018.7,
author = {Bandyapadhyay, Sayan and Bhowmick, Santanu and Inamdar, Tanmay and Varadarajan, Kasturi},
title = {{Capacitated Covering Problems in Geometric Spaces}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {7:1--7:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.7},
URN = {urn:nbn:de:0030-drops-87205},
doi = {10.4230/LIPIcs.SoCG.2018.7},
annote = {Keywords: Capacitated covering, Geometric set cover, LP rounding, Bi-criteria approximation}
}
Document
Faster Algorithms for some Optimization Problems on Collinear Points
Abstract
We propose faster algorithms for the following three optimization problems on n collinear points, i.e., points in dimension one. The first two problems are known to be NP-hard in higher dimensions.
1) Maximizing total area of disjoint disks: In this problem the goal is to maximize the total area of nonoverlapping disks centered at the points. Acharyya, De, and Nandy (2017) presented an O(n^2)-time algorithm for this problem. We present an optimal Theta(n)-time algorithm.
2) Minimizing sum of the radii of client-server coverage: The n points are partitioned into two sets, namely clients and servers. The goal is to minimize the sum of the radii of disks centered at servers such that every client is in some disk, i.e., in the coverage range of some server. Lev-Tov and Peleg (2005) presented an O(n^3)-time algorithm for this problem. We present an O(n^2)-time algorithm, thereby improving the running time by a factor of Theta(n).
3) Minimizing total area of point-interval coverage: The n input points belong to an interval I. The goal is to find a set of disks of minimum total area, covering I, such that every disk contains at least one input point. We present an algorithm that solves this problem in O(n^2) time.
Cite as
Ahmad Biniaz, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Ian Munro, and Michiel Smid. Faster Algorithms for some Optimization Problems on Collinear Points. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{biniaz_et_al:LIPIcs.SoCG.2018.8,
author = {Biniaz, Ahmad and Bose, Prosenjit and Carmi, Paz and Maheshwari, Anil and Munro, Ian and Smid, Michiel},
title = {{Faster Algorithms for some Optimization Problems on Collinear Points}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {8:1--8:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.8},
URN = {urn:nbn:de:0030-drops-87219},
doi = {10.4230/LIPIcs.SoCG.2018.8},
annote = {Keywords: collinear points, range assignment}
}
Document
Local Criteria for Triangulation of Manifolds
Abstract
We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.
Cite as
Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. Local Criteria for Triangulation of Manifolds. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2018.9,
author = {Boissonnat, Jean-Daniel and Dyer, Ramsay and Ghosh, Arijit and Wintraecken, Mathijs},
title = {{Local Criteria for Triangulation of Manifolds}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {9:1--9:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.9},
URN = {urn:nbn:de:0030-drops-87224},
doi = {10.4230/LIPIcs.SoCG.2018.9},
annote = {Keywords: manifold, simplicial complex, homeomorphism, triangulation}
}
Document
The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces
Abstract
In this paper we discuss three results. The first two concern general sets of positive reach: We first characterize the reach by means of a bound on the metric distortion between the distance in the ambient Euclidean space and the set of positive reach. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the distance between the points and the reach.
Cite as
Jean-Daniel Boissonnat, André Lieutier, and Mathijs Wintraecken. The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2018.10,
author = {Boissonnat, Jean-Daniel and Lieutier, Andr\'{e} and Wintraecken, Mathijs},
title = {{The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {10:1--10:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.10},
URN = {urn:nbn:de:0030-drops-87236},
doi = {10.4230/LIPIcs.SoCG.2018.10},
annote = {Keywords: Reach, Metric distortion, Manifolds, Convexity}
}
Document
Orthogonal Terrain Guarding is NP-complete
Abstract
A terrain is an x-monotone polygonal curve, i.e., successive vertices have increasing x-coordinates. Terrain Guarding can be seen as a special case of the famous art gallery problem where one has to place at most k guards on a terrain made of n vertices in order to fully see it. In 2010, King and Krohn showed that Terrain Guarding is NP-complete [SODA '10, SIAM J. Comput. '11] thereby solving a long-standing open question. They observe that their proof does not settle the complexity of Orthogonal Terrain Guarding where the terrain only consists of horizontal or vertical segments; those terrains are called rectilinear or orthogonal. Recently, Ashok et al. [SoCG'17] presented an FPT algorithm running in time k^{O(k)}n^{O(1)} for Dominating Set in the visibility graphs of rectilinear terrains without 180-degree vertices. They ask if Orthogonal Terrain Guarding is in P or NP-hard. In the same paper, they give a subexponential-time algorithm running in n^{O(sqrt n)} (actually even n^{O(sqrt k)}) for the general Terrain Guarding and notice that the hardness proof of King and Krohn only disproves a running time 2^{o(n^{1/4})} under the ETH. Hence, there is a significant gap between their 2^{O(n^{1/2} log n)}-algorithm and the no 2^{o(n^{1/4})} ETH-hardness implied by King and Krohn's result.
In this paper, we answer those two remaining questions. We adapt the gadgets of King and Krohn to rectilinear terrains in order to prove that even Orthogonal Terrain Guarding is NP-complete. Then, we show how their reduction from Planar 3-SAT (as well as our adaptation for rectilinear terrains) can actually be made linear (instead of quadratic).
Cite as
Édouard Bonnet and Panos Giannopoulos. Orthogonal Terrain Guarding is NP-complete. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bonnet_et_al:LIPIcs.SoCG.2018.11,
author = {Bonnet, \'{E}douard and Giannopoulos, Panos},
title = {{Orthogonal Terrain Guarding is NP-complete}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.11},
URN = {urn:nbn:de:0030-drops-87246},
doi = {10.4230/LIPIcs.SoCG.2018.11},
annote = {Keywords: terrain guarding, rectilinear terrain, computational complexity}
}
Document
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
Abstract
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Clique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show the rather surprising structural result that a disjoint union of cycles is the complement of a disk graph if and only if at most one of those cycles is of odd length. From that, we derive the first QPTAS and subexponential algorithm running in time 2^{O~(n^{2/3})} for Maximum Clique on disk graphs. In stark contrast, Maximum Clique on intersection graphs of filled ellipses or filled triangles is unlikely to have such algorithms, even when the ellipses are close to unit disks. Indeed, we show that there is a constant ratio of approximation which cannot be attained even in time 2^{n^{1-epsilon}}, unless the Exponential Time Hypothesis fails.
Cite as
Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, and Florian Sikora. QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bonnet_et_al:LIPIcs.SoCG.2018.12,
author = {Bonnet, \'{E}douard and Giannopoulos, Panos and Kim, Eun Jung and Rzazewski, Pawel and Sikora, Florian},
title = {{QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {12:1--12:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.12},
URN = {urn:nbn:de:0030-drops-87259},
doi = {10.4230/LIPIcs.SoCG.2018.12},
annote = {Keywords: disk graph, maximum clique, computational complexity}
}
Document
Computational Complexity of the Interleaving Distance
Abstract
The interleaving distance is arguably the most prominent distance measure in topological data analysis. In this paper, we provide bounds on the computational complexity of determining the interleaving distance in several settings. We show that the interleaving distance is NP-hard to compute for persistence modules valued in the category of vector spaces. In the specific setting of multidimensional persistent homology we show that the problem is at least as hard as a matrix invertibility problem. Furthermore, this allows us to conclude that the interleaving distance of interval decomposable modules depends on the characteristic of the field. Persistence modules valued in the category of sets are also studied. As a corollary, we obtain that the isomorphism problem for Reeb graphs is graph isomorphism complete.
Cite as
Håvard Bakke Bjerkevik and Magnus Bakke Botnan. Computational Complexity of the Interleaving Distance. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bjerkevik_et_al:LIPIcs.SoCG.2018.13,
author = {Bjerkevik, H\r{a}vard Bakke and Botnan, Magnus Bakke},
title = {{Computational Complexity of the Interleaving Distance}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {13:1--13:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.13},
URN = {urn:nbn:de:0030-drops-87268},
doi = {10.4230/LIPIcs.SoCG.2018.13},
annote = {Keywords: Persistent Homology, Interleavings, NP-hard}
}
Document
Sheaf-Theoretic Stratification Learning
Abstract
In this paper, we investigate a sheaf-theoretic interpretation of stratification learning. Motivated by the work of Alexandroff (1937) and McCord (1978), we aim to redirect efforts in the computational topology of triangulated compact polyhedra to the much more computable realm of sheaves on partially ordered sets. Our main result is the construction of stratification learning algorithms framed in terms of a sheaf on a partially ordered set with the Alexandroff topology. We prove that the resulting decomposition is the unique minimal stratification for which the strata are homogeneous and the given sheaf is constructible. In particular, when we choose to work with the local homology sheaf, our algorithm gives an alternative to the local homology transfer algorithm given in Bendich et al. (2012), and the cohomology stratification algorithm given in Nanda (2017). We envision that our sheaf-theoretic algorithm could give rise to a larger class of stratification beyond homology-based stratification. This approach also points toward future applications of sheaf theory in the study of topological data analysis by illustrating the utility of the language of sheaf theory in generalizing existing algorithms.
Cite as
Adam Brown and Bei Wang. Sheaf-Theoretic Stratification Learning. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{brown_et_al:LIPIcs.SoCG.2018.14,
author = {Brown, Adam and Wang, Bei},
title = {{Sheaf-Theoretic Stratification Learning}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {14:1--14:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.14},
URN = {urn:nbn:de:0030-drops-87270},
doi = {10.4230/LIPIcs.SoCG.2018.14},
annote = {Keywords: Sheaf theory, stratification learning, topological data analysis, stratification}
}
Document
Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension
Abstract
While persistent homology has taken strides towards becoming a widespread tool for data analysis, multidimensional persistence has proven more difficult to apply. One reason is the serious drawback of no longer having a concise and complete descriptor analogous to the persistence diagrams of the former. We propose a simple algebraic construction to illustrate the existence of infinite families of indecomposable persistence modules over regular grids of sufficient size. On top of providing a constructive proof of representation infinite type, we also provide realizations by topological spaces and Vietoris-Rips filtrations, showing that they can actually appear in real data and are not the product of degeneracies.
Cite as
Mickaël Buchet and Emerson G. Escolar. Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{buchet_et_al:LIPIcs.SoCG.2018.15,
author = {Buchet, Micka\"{e}l and Escolar, Emerson G.},
title = {{Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {15:1--15:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.15},
URN = {urn:nbn:de:0030-drops-87287},
doi = {10.4230/LIPIcs.SoCG.2018.15},
annote = {Keywords: persistent homology, multi-persistence, representation theory, quivers, commutative ladders, Vietoris-Rips filtration}
}
Document
Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data
Abstract
Robust estimators, like the median of a point set, are important for data analysis in the presence of outliers. We study robust estimators for locationally uncertain points with discrete distributions. That is, each point in a data set has a discrete probability distribution describing its location. The probabilistic nature of uncertain data makes it challenging to compute such estimators, since the true value of the estimator is now described by a distribution rather than a single point. We show how to construct and estimate the distribution of the median of a point set. Building the approximate support of the distribution takes near-linear time, and assigning probability to that support takes quadratic time. We also develop a general approximation technique for distributions of robust estimators with respect to ranges with bounded VC dimension. This includes the geometric median for high dimensions and the Siegel estimator for linear regression.
Cite as
Kevin Buchin, Jeff M. Phillips, and Pingfan Tang. Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{buchin_et_al:LIPIcs.SoCG.2018.16,
author = {Buchin, Kevin and Phillips, Jeff M. and Tang, Pingfan},
title = {{Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {16:1--16:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.16},
URN = {urn:nbn:de:0030-drops-87292},
doi = {10.4230/LIPIcs.SoCG.2018.16},
annote = {Keywords: Uncertain Data, Robust Estimators, Geometric Median, Tukey Median}
}
Document
Consistent Sets of Lines with no Colorful Incidence
Abstract
We consider incidences among colored sets of lines in {R}^d and examine whether the existence of certain concurrences between lines of k colors force the existence of at least one concurrence between lines of k+1 colors. This question is relevant for problems in 3D reconstruction in computer vision.
Cite as
Boris Bukh, Xavier Goaoc, Alfredo Hubard, and Matthew Trager. Consistent Sets of Lines with no Colorful Incidence. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bukh_et_al:LIPIcs.SoCG.2018.17,
author = {Bukh, Boris and Goaoc, Xavier and Hubard, Alfredo and Trager, Matthew},
title = {{Consistent Sets of Lines with no Colorful Incidence}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {17:1--17:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.17},
URN = {urn:nbn:de:0030-drops-87308},
doi = {10.4230/LIPIcs.SoCG.2018.17},
annote = {Keywords: Incidence geometry, image consistency, probabilistic construction, algebraic construction, projective configuration}
}
Document
The HOMFLY-PT Polynomial is Fixed-Parameter Tractable
Abstract
Many polynomial invariants of knots and links, including the Jones and HOMFLY-PT polynomials, are widely used in practice but #P-hard to compute. It was shown by Makowsky in 2001 that computing the Jones polynomial is fixed-parameter tractable in the treewidth of the link diagram, but the parameterised complexity of the more powerful HOMFLY-PT polynomial remained an open problem. Here we show that computing HOMFLY-PT is fixed-parameter tractable in the treewidth, and we give the first sub-exponential time algorithm to compute it for arbitrary links.
Cite as
Benjamin A. Burton. The HOMFLY-PT Polynomial is Fixed-Parameter Tractable. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{burton:LIPIcs.SoCG.2018.18,
author = {Burton, Benjamin A.},
title = {{The HOMFLY-PT Polynomial is Fixed-Parameter Tractable}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {18:1--18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.18},
URN = {urn:nbn:de:0030-drops-87311},
doi = {10.4230/LIPIcs.SoCG.2018.18},
annote = {Keywords: Knot theory, knot invariants, parameterised complexity}
}
Document
Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises
Abstract
We examine volume computation of general-dimensional polytopes and more general convex bodies, defined as the intersection of a simplex by a family of parallel hyperplanes, and another family of parallel hyperplanes or a family of concentric ellipsoids. Such convex bodies appear in modeling and predicting financial crises. The impact of crises on the economy (labor, income, etc.) makes its detection of prime interest for the public in general and for policy makers in particular. Certain features of dependencies in the markets clearly identify times of turmoil. We describe the relationship between asset characteristics by means of a copula; each characteristic is either a linear or quadratic form of the portfolio components, hence the copula can be constructed by computing volumes of convex bodies.
We design and implement practical algorithms in the exact and approximate setting, we experimentally juxtapose them and study the tradeoff of exactness and accuracy for speed. We analyze the following methods in order of increasing generality: rejection sampling relying on uniformly sampling the simplex, which is the fastest approach, but inaccurate for small volumes; exact formulae based on the computation of integrals of probability distribution functions, which are the method of choice for intersections with a single hyperplane; an optimized Lawrence sign decomposition method, since the polytopes at hand are shown to be simple with additional structure; Markov chain Monte Carlo algorithms using random walks based on the hit-and-run paradigm generalized to nonlinear convex bodies and relying on new methods for computing a ball enclosed in the given body, such as a second-order cone program; the latter is experimentally extended to non-convex bodies with very encouraging results. Our C++ software, based on CGAL and Eigen and available on github, is shown to be very effective in up to 100 dimensions. Our results offer novel, effective means of computing portfolio dependencies and an indicator of financial crises, which is shown to correctly identify past crises.
Cite as
Ludovic Calès, Apostolos Chalkis, Ioannis Z. Emiris, and Vissarion Fisikopoulos. Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{cales_et_al:LIPIcs.SoCG.2018.19,
author = {Cal\`{e}s, Ludovic and Chalkis, Apostolos and Emiris, Ioannis Z. and Fisikopoulos, Vissarion},
title = {{Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {19:1--19:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.19},
URN = {urn:nbn:de:0030-drops-87328},
doi = {10.4230/LIPIcs.SoCG.2018.19},
annote = {Keywords: Polytope volume, convex body, simplex, sampling, financial portfolio}
}
Document
Subquadratic Encodings for Point Configurations
Abstract
For many algorithms dealing with sets of points in the plane, the only relevant information carried by the input is the combinatorial configuration of the points: the orientation of each triple of points in the set (clockwise, counterclockwise, or collinear). This information is called the order type of the point set. In the dual, realizable order types and abstract order types are combinatorial analogues of line arrangements and pseudoline arrangements. Too often in the literature we analyze algorithms in the real-RAM model for simplicity, putting aside the fact that computers as we know them cannot handle arbitrary real numbers without some sort of encoding. Encoding an order type by the integer coordinates of a realizing point set is known to yield doubly exponential coordinates in some cases. Other known encodings can achieve quadratic space or fast orientation queries, but not both. In this contribution, we give a compact encoding for abstract order types that allows efficient query of the orientation of any triple: the encoding uses O(n^2) bits and an orientation query takes O(log n) time in the word-RAM model with word size w >= log n. This encoding is space-optimal for abstract order types. We show how to shorten the encoding to O(n^2 {(log log n)}^2 / log n) bits for realizable order types, giving the first subquadratic encoding for those order types with fast orientation queries. We further refine our encoding to attain O(log n/log log n) query time at the expense of a negligibly larger space requirement. In the realizable case, we show that all those encodings can be computed efficiently. Finally, we generalize our results to the encoding of point configurations in higher dimension.
Cite as
Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, and Aurélien Ooms. Subquadratic Encodings for Point Configurations. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{cardinal_et_al:LIPIcs.SoCG.2018.20,
author = {Cardinal, Jean and Chan, Timothy M. and Iacono, John and Langerman, Stefan and Ooms, Aur\'{e}lien},
title = {{Subquadratic Encodings for Point Configurations}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {20:1--20:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.20},
URN = {urn:nbn:de:0030-drops-87337},
doi = {10.4230/LIPIcs.SoCG.2018.20},
annote = {Keywords: point configuration, order type, chirotope, succinct data structure}
}
Document
Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces
Abstract
We study the problem of finding a minimum-distortion embedding of the shortest path metric of an unweighted graph into a "simpler" metric X. Computing such an embedding (exactly or approximately) is a non-trivial task even when X is the metric induced by a path, or, equivalently, the real line. In this paper we give approximation and fixed-parameter tractable (FPT) algorithms for minimum-distortion embeddings into the metric of a subdivision of some fixed graph H, or, equivalently, into any fixed 1-dimensional simplicial complex. More precisely, we study the following problem: For given graphs G, H and integer c, is it possible to embed G with distortion c into a graph homeomorphic to H? Then embedding into the line is the special case H=K_2, and embedding into the cycle is the case H=K_3, where K_k denotes the complete graph on k vertices. For this problem we give
- an approximation algorithm, which in time f(H)* poly (n), for some function f, either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion poly(c);
- an exact algorithm, which in time f'(H, c)* poly (n), for some function f', either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion c. Prior to our work, poly(OPT)-approximation or FPT algorithms were known only for embedding into paths and trees of bounded degrees.
Cite as
Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Anastasios Sidiropoulos. Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{carpenter_et_al:LIPIcs.SoCG.2018.21,
author = {Carpenter, Timothy and Fomin, Fedor V. and Lokshtanov, Daniel and Saurabh, Saket and Sidiropoulos, Anastasios},
title = {{Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {21:1--21:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.21},
URN = {urn:nbn:de:0030-drops-87344},
doi = {10.4230/LIPIcs.SoCG.2018.21},
annote = {Keywords: Metric embeddings, minimum-distortion embeddings, 1-dimensional simplicial complex, Fixed-parameter tractable algorithms, Approximation algorithms}
}
Document
Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs
Abstract
In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov hyperbolicity for geodesic metric spaces can be reduced to the study of graph hyperbolicity. Our main contribution in this note is a new characterization of hyperbolicity for graphs (and for complete geodesic metric spaces). This characterization has algorithmic implications in the field of large-scale network analysis, which was one of our initial motivations. A sharp estimate of graph hyperbolicity is useful, {e.g.}, in embedding an undirected graph into hyperbolic space with minimum distortion [Verbeek and Suri, SoCG'14]. The hyperbolicity of a graph can be computed in polynomial-time, however it is unlikely that it can be done in subcubic time. This makes this parameter difficult to compute or to approximate on large graphs. Using our new characterization of graph hyperbolicity, we provide a simple factor 8 approximation algorithm for computing the hyperbolicity of an n-vertex graph G=(V,E) in optimal time O(n^2) (assuming that the input is the distance matrix of the graph). This algorithm leads to constant factor approximations of other graph-parameters related to hyperbolicity (thinness, slimness, and insize). We also present the first efficient algorithms for exact computation of these parameters. All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space.
Cite as
Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chalopin_et_al:LIPIcs.SoCG.2018.22,
author = {Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Dragan, Feodor F. and Ducoffe, Guillaume and Mohammed, Abdulhakeem and Vax\`{e}s, Yann},
title = {{Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {22:1--22:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.22},
URN = {urn:nbn:de:0030-drops-87356},
doi = {10.4230/LIPIcs.SoCG.2018.22},
annote = {Keywords: Gromov hyperbolicity, Graphs, Geodesic metric spaces, Approximation algorithms}
}
Document
Tree Drawings Revisited
Abstract
We make progress on a number of open problems concerning the area requirement for drawing trees on a grid. We prove that
1) every tree of size n (with arbitrarily large degree) has a straight-line drawing with area n2^{O(sqrt{log log n log log log n})}, improving the longstanding O(n log n) bound;
2) every tree of size n (with arbitrarily large degree) has a straight-line upward drawing with area n sqrt{log n}(log log n)^{O(1)}, improving the longstanding O(n log n) bound;
3) every binary tree of size n has a straight-line orthogonal drawing with area n2^{O(log^*n)}, improving the previous O(n log log n) bound by Shin, Kim, and Chwa (1996) and Chan, Goodrich, Kosaraju, and Tamassia (1996);
4) every binary tree of size n has a straight-line order-preserving drawing with area n2^{O(log^*n)}, improving the previous O(n log log n) bound by Garg and Rusu (2003);
5) every binary tree of size n has a straight-line orthogonal order-preserving drawing with area n2^{O(sqrt{log n})}, improving the O(n^{3/2}) previous bound by Frati (2007).
Cite as
Timothy M. Chan. Tree Drawings Revisited. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chan:LIPIcs.SoCG.2018.23,
author = {Chan, Timothy M.},
title = {{Tree Drawings Revisited}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {23:1--23:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.23},
URN = {urn:nbn:de:0030-drops-87364},
doi = {10.4230/LIPIcs.SoCG.2018.23},
annote = {Keywords: graph drawing, trees, recursion}
}
Document
Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs
Abstract
We present the first near-linear-time (1 + epsilon)-approximation algorithm for the diameter of a weighted unit-disk graph of n vertices, running in O(n log^2 n) time, for any constant epsilon>0, improving the near-O(n^{3/2})-time algorithm of Gao and Zhang [STOC 2003]. Using similar ideas, we can construct a (1+epsilon)-approximate distance oracle for weighted unit-disk graphs with O(1) query time, with a similar improvement in the preprocessing time, from near O(n^{3/2}) to O(n log^3 n). We also obtain new results for a number of other related problems in the weighted unit-disk graph metric, such as the radius and bichromatic closest pair.
As a further application, we use our new distance oracle, along with additional ideas, to solve the (1 + epsilon)-approximate all-pairs bounded-leg shortest paths problem for a set of n planar points, with near O(n^{2.579}) preprocessing time, O(n^2 log n) space, and O(log{log n}) query time, improving thus the near-cubic preprocessing bound by Roditty and Segal [SODA 2007].
Cite as
Timothy M. Chan and Dimitrios Skrepetos. Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chan_et_al:LIPIcs.SoCG.2018.24,
author = {Chan, Timothy M. and Skrepetos, Dimitrios},
title = {{Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {24:1--24:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.24},
URN = {urn:nbn:de:0030-drops-87375},
doi = {10.4230/LIPIcs.SoCG.2018.24},
annote = {Keywords: shortest paths, distance oracles, unit-disk graphs, planar graphs}
}
Document
Dynamic Planar Orthogonal Point Location in Sublogarithmic Time
Abstract
We study a longstanding problem in computational geometry: dynamic 2-d orthogonal point location, i.e., vertical ray shooting among n horizontal line segments. We present a data structure achieving O(log n / log log n) optimal expected query time and O(log^{1/2+epsilon} n) update time (amortized) in the word-RAM model for any constant epsilon>0, under the assumption that the x-coordinates are integers bounded polynomially in n. This substantially improves previous results of Giyora and Kaplan [SODA 2007] and Blelloch [SODA 2008] with O(log n) query and update time, and of Nekrich (2010) with O(log n / log log n) query time and O(log^{1+epsilon} n) update time. Our result matches the best known upper bound for simpler problems such as dynamic 2-d dominance range searching.
We also obtain similar bounds for orthogonal line segment intersection reporting queries, vertical ray stabbing, and vertical stabbing-max, improving previous bounds, respectively, of Blelloch [SODA 2008] and Mortensen [SODA 2003], of Tao (2014), and of Agarwal, Arge, and Yi [SODA 2005] and Nekrich [ISAAC 2011].
Cite as
Timothy M. Chan and Konstantinos Tsakalidis. Dynamic Planar Orthogonal Point Location in Sublogarithmic Time. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chan_et_al:LIPIcs.SoCG.2018.25,
author = {Chan, Timothy M. and Tsakalidis, Konstantinos},
title = {{Dynamic Planar Orthogonal Point Location in Sublogarithmic Time}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {25:1--25:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.25},
URN = {urn:nbn:de:0030-drops-87382},
doi = {10.4230/LIPIcs.SoCG.2018.25},
annote = {Keywords: dynamic data structures, point location, word RAM}
}
Document
The Density of Expected Persistence Diagrams and its Kernel Based Estimation
Abstract
Persistence diagrams play a fundamental role in Topological Data Analysis where they are used as topological descriptors of filtrations built on top of data. They consist in discrete multisets of points in the plane R^2 that can equivalently be seen as discrete measures in R^2. When the data come as a random point cloud, these discrete measures become random measures whose expectation is studied in this paper. First, we show that for a wide class of filtrations, including the Cech and Rips-Vietoris filtrations, the expected persistence diagram, that is a deterministic measure on R^2, has a density with respect to the Lebesgue measure. Second, building on the previous result we show that the persistence surface recently introduced in [Adams et al., 2017] can be seen as a kernel estimator of this density. We propose a cross-validation scheme for selecting an optimal bandwidth, which is proven to be a consistent procedure to estimate the density.
Cite as
Frédéric Chazal and Vincent Divol. The Density of Expected Persistence Diagrams and its Kernel Based Estimation. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chazal_et_al:LIPIcs.SoCG.2018.26,
author = {Chazal, Fr\'{e}d\'{e}ric and Divol, Vincent},
title = {{The Density of Expected Persistence Diagrams and its Kernel Based Estimation}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {26:1--26:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.26},
URN = {urn:nbn:de:0030-drops-87395},
doi = {10.4230/LIPIcs.SoCG.2018.26},
annote = {Keywords: topological data analysis, persistence diagrams, subanalytic geometry}
}
Document
Embedding Graphs into Two-Dimensional Simplicial Complexes
Abstract
We consider the problem of deciding whether an input graph G admits a topological embedding into a two-dimensional simplicial complex C. This problem includes, among others, the embeddability problem of a graph on a surface and the topological crossing number of a graph, but is more general.
The problem is NP-complete when C is part of the input, and we give a polynomial-time algorithm if the complex C is fixed.
Our strategy is to reduce the problem to an embedding extension problem on a surface, which has the following form: Given a subgraph H' of a graph G', and an embedding of H' on a surface S, can that embedding be extended to an embedding of G' on S? Such problems can be solved, in turn, using a key component in Mohar's algorithm to decide the embeddability of a graph on a fixed surface (STOC 1996, SIAM J. Discr. Math. 1999).
Cite as
Éric Colin de Verdière, Thomas Magnard, and Bojan Mohar. Embedding Graphs into Two-Dimensional Simplicial Complexes. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{verdiere_et_al:LIPIcs.SoCG.2018.27,
author = {Verdi\`{e}re, \'{E}ric Colin de and Magnard, Thomas and Mohar, Bojan},
title = {{Embedding Graphs into Two-Dimensional Simplicial Complexes}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {27:1--27:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.27},
URN = {urn:nbn:de:0030-drops-87401},
doi = {10.4230/LIPIcs.SoCG.2018.27},
annote = {Keywords: computational topology, embedding, simplicial complex, graph, surface}
}
Document
On the Complexity of Closest Pair via Polar-Pair of Point-Sets
Abstract
Every graph G can be represented by a collection of equi-radii spheres in a d-dimensional metric Delta such that there is an edge uv in G if and only if the spheres corresponding to u and v intersect. The smallest integer d such that G can be represented by a collection of spheres (all of the same radius) in Delta is called the sphericity of G, and if the collection of spheres are non-overlapping, then the value d is called the contact-dimension of G. In this paper, we study the sphericity and contact dimension of the complete bipartite graph K_{n,n} in various L^p-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.
Cite as
Roee David, Karthik C. S., and Bundit Laekhanukit. On the Complexity of Closest Pair via Polar-Pair of Point-Sets. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{david_et_al:LIPIcs.SoCG.2018.28,
author = {David, Roee and C. S., Karthik and Laekhanukit, Bundit},
title = {{On the Complexity of Closest Pair via Polar-Pair of Point-Sets}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {28:1--28:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.28},
URN = {urn:nbn:de:0030-drops-87412},
doi = {10.4230/LIPIcs.SoCG.2018.28},
annote = {Keywords: Contact dimension, Sphericity, Closest Pair, Fine-Grained Complexity}
}
Document
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
Abstract
We present a number of breakthroughs for coordinated motion planning, in which the objective is to reconfigure a swarm of labeled convex objects by a combination of parallel, continuous, collision-free translations into a given target arrangement. Problems of this type can be traced back to the classic work of Schwartz and Sharir (1983), who gave a method for deciding the existence of a coordinated motion for a set of disks between obstacles; their approach is polynomial in the complexity of the obstacles, but exponential in the number of disks. Despite a broad range of other non-trivial results for multi-object motion planning, previous work has largely focused on sequential schedules, in which one robot moves at a time, with objectives such as the number of moves; attempts to minimize the overall makespan of a coordinated parallel motion schedule (with many robots moving simultaneously) have defied all attempts at establishing the complexity in the absence of obstacles, as well as the existence of efficient approximation methods.
We resolve these open problems by developing a framework that provides constant-factor approximation algorithms for minimizing the execution time of a coordinated, parallel motion plan for a swarm of robots in the absence of obstacles, provided their arrangement entails some amount of separability. In fact, our algorithm achieves constant stretch factor: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot) is O(d). Various extensions include unlabeled robots and different classes of robots. We also resolve the complexity of finding a reconfiguration plan with minimal execution time by proving that this is NP-hard, even for a grid arrangement without any stationary obstacles. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) may be required. On the positive side, we establish a stretch factor of O(N^{1/2}) even in this case. The intricate difficulties of computing precise optimal solutions are demonstrated by the seemingly simple case of just two disks, which is shown to be excruciatingly difficult to solve to optimality.
Cite as
Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer. Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{demaine_et_al:LIPIcs.SoCG.2018.29,
author = {Demaine, Erik D. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Scheffer, Christian and Meijer, Henk},
title = {{Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {29:1--29:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.29},
URN = {urn:nbn:de:0030-drops-87423},
doi = {10.4230/LIPIcs.SoCG.2018.29},
annote = {Keywords: Robot swarms, coordinated motion planning, parallel motion, makespan, bounded stretch, complexity, approximation}
}
Document
3D Snap Rounding
Abstract
Let P be a set of n polygons in R^3, each of constant complexity and with pairwise disjoint interiors. We propose a rounding algorithm that maps P to a simplicial complex Q whose vertices have integer coordinates. Every face of P is mapped to a set of faces (or edges or vertices) of Q and the mapping from P to Q can be done through a continuous motion of the faces such that (i) the L_infty Hausdorff distance between a face and its image during the motion is at most 3/2 and (ii) if two points become equal during the motion, they remain equal through the rest of the motion. In the worst case, the size of Q is O(n^{15}) and the time complexity of the algorithm is O(n^{19}) but, under reasonable hypotheses, these complexities decrease to O(n^{5}) and O(n^{6}sqrt{n}).
Cite as
Olivier Devillers, Sylvain Lazard, and William J. Lenhart. 3D Snap Rounding. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{devillers_et_al:LIPIcs.SoCG.2018.30,
author = {Devillers, Olivier and Lazard, Sylvain and Lenhart, William J.},
title = {{3D Snap Rounding}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {30:1--30:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.30},
URN = {urn:nbn:de:0030-drops-87438},
doi = {10.4230/LIPIcs.SoCG.2018.30},
annote = {Keywords: Geometric algorithms, Robustness, Fixed-precision computations}
}
Document
Graph Reconstruction by Discrete Morse Theory
Abstract
Recovering hidden graph-like structures from potentially noisy data is a fundamental task in modern data analysis. Recently, a persistence-guided discrete Morse-based framework to extract a geometric graph from low-dimensional data has become popular. However, to date, there is very limited theoretical understanding of this framework in terms of graph reconstruction. This paper makes a first step towards closing this gap. Specifically, first, leveraging existing theoretical understanding of persistence-guided discrete Morse cancellation, we provide a simplified version of the existing discrete Morse-based graph reconstruction algorithm. We then introduce a simple and natural noise model and show that the aforementioned framework can correctly reconstruct a graph under this noise model, in the sense that it has the same loop structure as the hidden ground-truth graph, and is also geometrically close. We also provide some experimental results for our simplified graph-reconstruction algorithm.
Cite as
Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Graph Reconstruction by Discrete Morse Theory. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{dey_et_al:LIPIcs.SoCG.2018.31,
author = {Dey, Tamal K. and Wang, Jiayuan and Wang, Yusu},
title = {{Graph Reconstruction by Discrete Morse Theory}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {31:1--31:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.31},
URN = {urn:nbn:de:0030-drops-87443},
doi = {10.4230/LIPIcs.SoCG.2018.31},
annote = {Keywords: graph reconstruction, discrete Morse theory, persistence}
}
Document
Computing Bottleneck Distance for 2-D Interval Decomposable Modules
Abstract
Computation of the interleaving distance between persistence modules is a central task in topological data analysis. For 1-D persistence modules, thanks to the isometry theorem, this can be done by computing the bottleneck distance with known efficient algorithms. The question is open for most n-D persistence modules, n>1, because of the well recognized complications of the indecomposables. Here, we consider a reasonably complicated class called 2-D interval decomposable modules whose indecomposables may have a description of non-constant complexity. We present a polynomial time algorithm to compute the bottleneck distance for these modules from indecomposables, which bounds the interleaving distance from above, and give another algorithm to compute a new distance called dimension distance that bounds it from below.
Cite as
Tamal K. Dey and Cheng Xin. Computing Bottleneck Distance for 2-D Interval Decomposable Modules. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{dey_et_al:LIPIcs.SoCG.2018.32,
author = {Dey, Tamal K. and Xin, Cheng},
title = {{Computing Bottleneck Distance for 2-D Interval Decomposable Modules}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {32:1--32:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.32},
URN = {urn:nbn:de:0030-drops-87453},
doi = {10.4230/LIPIcs.SoCG.2018.32},
annote = {Keywords: Persistence modules, bottleneck distance, interleaving distance}
}
Document
Structure and Generation of Crossing-Critical Graphs
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 c=1 there are only two such graphs without degree-2 vertices, K_5 and K_{3,3}, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.
Cite as
Zdenek Dvorák, Petr Hlinený, and Bojan Mohar. Structure and Generation of Crossing-Critical Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{dvorak_et_al:LIPIcs.SoCG.2018.33,
author = {Dvor\'{a}k, Zdenek and Hlinen\'{y}, Petr and Mohar, Bojan},
title = {{Structure and Generation of Crossing-Critical Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {33:1--33:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.33},
URN = {urn:nbn:de:0030-drops-87460},
doi = {10.4230/LIPIcs.SoCG.2018.33},
annote = {Keywords: crossing number, crossing-critical, path-width, exhaustive generation}
}
Document
The Multi-cover Persistence of Euclidean Balls
Abstract
Given a locally finite X subseteq R^d and a radius r >= 0, the k-fold cover of X and r consists of all points in R^d that have k or more points of X within distance r. We consider two filtrations - one in scale obtained by fixing k and increasing r, and the other in depth obtained by fixing r and decreasing k - and we compute the persistence diagrams of both. While standard methods suffice for the filtration in scale, we need novel geometric and topological concepts for the filtration in depth. In particular, we introduce a rhomboid tiling in R^{d+1} whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module from Delaunay mosaics that is isomorphic to the persistence module of the multi-covers.
Cite as
Herbert Edelsbrunner and Georg Osang. The Multi-cover Persistence of Euclidean Balls. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2018.34,
author = {Edelsbrunner, Herbert and Osang, Georg},
title = {{The Multi-cover Persistence of Euclidean Balls}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {34:1--34:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.34},
URN = {urn:nbn:de:0030-drops-87471},
doi = {10.4230/LIPIcs.SoCG.2018.34},
annote = {Keywords: Delaunay mosaics, hyperplane arrangements, discrete Morse theory, zigzag modules, persistent homology}
}
Document
Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry
Abstract
Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex.
Cite as
Herbert Edelsbrunner, Ziga Virk, and Hubert Wagner. Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2018.35,
author = {Edelsbrunner, Herbert and Virk, Ziga and Wagner, Hubert},
title = {{Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {35:1--35:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.35},
URN = {urn:nbn:de:0030-drops-87487},
doi = {10.4230/LIPIcs.SoCG.2018.35},
annote = {Keywords: Bregman divergence, smallest enclosing spheres, Chernoff points, convexity, barycenter polytopes}
}
Document
Near Isometric Terminal Embeddings for Doubling Metrics
Abstract
Given a metric space (X,d), a set of terminals K subseteq X, and a parameter t >= 1, we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in K x X up to a factor of t, and have small size (e.g. number of edges for spanners, dimension for embeddings). While such terminal (aka source-wise) metric structures are known to exist in several settings, no terminal spanner or embedding with distortion close to 1, i.e., t=1+epsilon for some small 0<epsilon<1, is currently known.
Here we devise such terminal metric structures for doubling metrics, and show that essentially any metric structure with distortion 1+epsilon and size s(|X|) has its terminal counterpart, with distortion 1+O(epsilon) and size s(|K|)+1. In particular, for any doubling metric on n points, a set of k=o(n) terminals, and constant 0<epsilon<1, there exists
- A spanner with stretch 1+epsilon for pairs in K x X, with n+o(n) edges.
- A labeling scheme with stretch 1+epsilon for pairs in K x X, with label size ~~ log k.
- An embedding into l_infty^d with distortion 1+epsilon for pairs in K x X, where d=O(log k). Moreover, surprisingly, the last two results apply if only K is a doubling metric, while X can be arbitrary.
Cite as
Michael Elkin and Ofer Neiman. Near Isometric Terminal Embeddings for Doubling Metrics. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{elkin_et_al:LIPIcs.SoCG.2018.36,
author = {Elkin, Michael and Neiman, Ofer},
title = {{Near Isometric Terminal Embeddings for Doubling Metrics}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {36:1--36:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.36},
URN = {urn:nbn:de:0030-drops-87498},
doi = {10.4230/LIPIcs.SoCG.2018.36},
annote = {Keywords: metric embedding, spanners, doubling metrics}
}
Document
Products of Euclidean Metrics and Applications to Proximity Questions among Curves
Abstract
The problem of Approximate Nearest Neighbor (ANN) search is fundamental in computer science and has benefited from significant progress in the past couple of decades. However, most work has been devoted to pointsets whereas complex shapes have not been sufficiently treated. Here, we focus on distance functions between discretized curves in Euclidean space: they appear in a wide range of applications, from road segments and molecular backbones to time-series in general dimension. For l_p-products of Euclidean metrics, for any p >= 1, we design simple and efficient data structures for ANN, based on randomized projections, which are of independent interest. They serve to solve proximity problems under a notion of distance between discretized curves, which generalizes both discrete Fréchet and Dynamic Time Warping distances. These are the most popular and practical approaches to comparing such curves. We offer the first data structures and query algorithms for ANN with arbitrarily good approximation factor, at the expense of increasing space usage and preprocessing time over existing methods. Query time complexity is comparable or significantly improved by our algorithms; our approach is especially efficient when the length of the curves is bounded.
Cite as
Ioannis Z. Emiris and Ioannis Psarros. Products of Euclidean Metrics and Applications to Proximity Questions among Curves. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{emiris_et_al:LIPIcs.SoCG.2018.37,
author = {Emiris, Ioannis Z. and Psarros, Ioannis},
title = {{Products of Euclidean Metrics and Applications to Proximity Questions among Curves}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {37:1--37:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.37},
URN = {urn:nbn:de:0030-drops-87504},
doi = {10.4230/LIPIcs.SoCG.2018.37},
annote = {Keywords: Approximate nearest neighbor, polygonal curves, Fr\'{e}chet distance, dynamic time warping}
}
Document
Rainbow Cycles in Flip Graphs
Abstract
The flip graph of triangulations has as vertices all triangulations of a convex n-gon, and an edge between any two triangulations that differ in exactly one edge. An r-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly r times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of r-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex n-gon, the flip graph of plane spanning trees on an arbitrary set of n points, and the flip graph of non-crossing perfect matchings on a set of n points in convex position. In addition, we consider two flip graphs on classes of non-geometric objects: the flip graph of permutations of {1,2,...,n } and the flip graph of k-element subsets of {1,2,...,n }. In each of the five settings, we prove the existence and non-existence of rainbow cycles for different values of r, n and k.
Cite as
Stefan Felsner, Linda Kleist, Torsten Mütze, and Leon Sering. Rainbow Cycles in Flip Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{felsner_et_al:LIPIcs.SoCG.2018.38,
author = {Felsner, Stefan and Kleist, Linda and M\"{u}tze, Torsten and Sering, Leon},
title = {{Rainbow Cycles in Flip Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {38:1--38:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.38},
URN = {urn:nbn:de:0030-drops-87514},
doi = {10.4230/LIPIcs.SoCG.2018.38},
annote = {Keywords: flip graph, cycle, rainbow, Gray code, triangulation, spanning tree, matching, permutation, subset, combination}
}
Document
Hanani-Tutte for Approximating Maps of Graphs
Abstract
We resolve in the affirmative conjectures of A. Skopenkov and Repovs (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.
Cite as
Radoslav Fulek and Jan Kyncl. Hanani-Tutte for Approximating Maps of Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{fulek_et_al:LIPIcs.SoCG.2018.39,
author = {Fulek, Radoslav and Kyncl, Jan},
title = {{Hanani-Tutte for Approximating Maps of Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {39:1--39:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.39},
URN = {urn:nbn:de:0030-drops-87527},
doi = {10.4230/LIPIcs.SoCG.2018.39},
annote = {Keywords: Hanani-Tutte theorem, graph embedding, map approximation, weak embedding, clustered planarity}
}
Document
The Z_2-Genus of Kuratowski Minors
Abstract
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 is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t x t grid or one of the following so-called t-Kuratowski graphs: K_{3,t}, or t copies of K_5 or K_{3,3} sharing at most 2 common vertices. We show that the Z_2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its Z_2-genus, solving a problem posed by Schaefer and Stefankovic, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces.
Cite as
Radoslav Fulek and Jan Kyncl. The Z_2-Genus of Kuratowski Minors. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{fulek_et_al:LIPIcs.SoCG.2018.40,
author = {Fulek, Radoslav and Kyncl, Jan},
title = {{The Z\underline2-Genus of Kuratowski Minors}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {40:1--40:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.40},
URN = {urn:nbn:de:0030-drops-87539},
doi = {10.4230/LIPIcs.SoCG.2018.40},
annote = {Keywords: Hanani-Tutte theorem, genus of a graph, Z\underline2-genus of a graph, Kuratowski graph}
}
Document
Shellability is NP-Complete
Abstract
We prove that for every d >= 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d >= 2 and k >= 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d >= 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.
Cite as
Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Shellability is NP-Complete. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{goaoc_et_al:LIPIcs.SoCG.2018.41,
author = {Goaoc, Xavier and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
title = {{Shellability is NP-Complete}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {41:1--41:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.41},
URN = {urn:nbn:de:0030-drops-87542},
doi = {10.4230/LIPIcs.SoCG.2018.41},
annote = {Keywords: Shellability, simplicial complexes, NP-completeness, collapsibility}
}
Document
Optimal Morphs of Planar Orthogonal Drawings
Abstract
We describe an algorithm that morphs between two planar orthogonal drawings Gamma_I and Gamma_O of a connected graph G, while preserving planarity and orthogonality. Necessarily Gamma_I and Gamma_O share the same combinatorial embedding. Our morph uses a linear number of linear morphs (linear interpolations between two drawings) and preserves linear complexity throughout the process, thereby answering an open question from Biedl et al. [Biedl et al., 2013].
Our algorithm first unifies the two drawings to ensure an equal number of (virtual) bends on each edge. We then interpret bends as vertices which form obstacles for so-called wires: horizontal and vertical lines separating the vertices of Gamma_O. We can find corresponding wires in Gamma_I that share topological properties with the wires in Gamma_O. The structural difference between the two drawings can be captured by the spirality of the wires in Gamma_I, which guides our morph from Gamma_I to Gamma_O.
Cite as
Arthur van Goethem and Kevin Verbeek. Optimal Morphs of Planar Orthogonal Drawings. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{vangoethem_et_al:LIPIcs.SoCG.2018.42,
author = {van Goethem, Arthur and Verbeek, Kevin},
title = {{Optimal Morphs of Planar Orthogonal Drawings}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {42:1--42:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.42},
URN = {urn:nbn:de:0030-drops-87550},
doi = {10.4230/LIPIcs.SoCG.2018.42},
annote = {Keywords: Homotopy, Morphing, Orthogonal drawing, Spirality}
}
Document
Computational Topology and the Unique Games Conjecture
Abstract
Covering spaces of graphs have long been useful for studying expanders (as "graph lifts") and unique games (as the "label-extended graph"). In this paper we advocate for the thesis that there is a much deeper relationship between computational topology and the Unique Games Conjecture. Our starting point is Linial's 2005 observation that the only known problems whose inapproximability is equivalent to the Unique Games Conjecture - Unique Games and Max-2Lin - are instances of Maximum Section of a Covering Space on graphs. We then observe that the reduction between these two problems (Khot-Kindler-Mossel-O'Donnell, FOCS '04; SICOMP '07) gives a well-defined map of covering spaces. We further prove that inapproximability for Maximum Section of a Covering Space on (cell decompositions of) closed 2-manifolds is also equivalent to the Unique Games Conjecture. This gives the first new "Unique Games-complete" problem in over a decade.
Our results partially settle an open question of Chen and Freedman (SODA, 2010; Disc. Comput. Geom., 2011) from computational topology, by showing that their question is almost equivalent to the Unique Games Conjecture. (The main difference is that they ask for inapproximability over Z_2, and we show Unique Games-completeness over Z_k for large k.) This equivalence comes from the fact that when the structure group G of the covering space is Abelian - or more generally for principal G-bundles - Maximum Section of a G-Covering Space is the same as the well-studied problem of 1-Homology Localization.
Although our most technically demanding result is an application of Unique Games to computational topology, we hope that our observations on the topological nature of the Unique Games Conjecture will lead to applications of algebraic topology to the Unique Games Conjecture in the future.
Cite as
Joshua A. Grochow and Jamie Tucker-Foltz. Computational Topology and the Unique Games Conjecture. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{grochow_et_al:LIPIcs.SoCG.2018.43,
author = {Grochow, Joshua A. and Tucker-Foltz, Jamie},
title = {{Computational Topology and the Unique Games Conjecture}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {43:1--43:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.43},
URN = {urn:nbn:de:0030-drops-87566},
doi = {10.4230/LIPIcs.SoCG.2018.43},
annote = {Keywords: Unique Games Conjecture, homology localization, inapproximability, computational topology, graph lift, covering graph, permutation voltage graph, cell}
}
Document
Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality
Abstract
We consider practical methods for the problem of finding a minimum-weight triangulation (MWT) of a planar point set, a classic problem of computational geometry with many applications. While Mulzer and Rote proved in 2006 that computing an MWT is NP-hard, Beirouti and Snoeyink showed in 1998 that computing provably optimal solutions for MWT instances of up to 80,000 uniformly distributed points is possible, making use of clever heuristics that are based on geometric insights. We show that these techniques can be refined and extended to instances of much bigger size and different type, based on an array of modifications and parallelizations in combination with more efficient geometric encodings and data structures. As a result, we are able to solve MWT instances with up to 30,000,000 uniformly distributed points in less than 4 minutes to provable optimality. Moreover, we can compute optimal solutions for a vast array of other benchmark instances that are not uniformly distributed, including normally distributed instances (up to 30,000,000 points), all point sets in the TSPLIB (up to 85,900 points), and VLSI instances with up to 744,710 points. This demonstrates that from a practical point of view, MWT instances can be handled quite well, despite their theoretical difficulty.
Cite as
Andreas Haas. Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{haas:LIPIcs.SoCG.2018.44,
author = {Haas, Andreas},
title = {{Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {44:1--44:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.44},
URN = {urn:nbn:de:0030-drops-87576},
doi = {10.4230/LIPIcs.SoCG.2018.44},
annote = {Keywords: computational geometry, minimum-weight triangulation}
}
Document
Dynamic Smooth Compressed Quadtrees
Abstract
We introduce dynamic smooth (a.k.a. balanced) compressed quadtrees with worst-case constant time updates in constant dimensions. We distinguish two versions of the problem. First, we show that quadtrees as a space-division data structure can be made smooth and dynamic subject to split and merge operations on the quadtree cells. Second, we show that quadtrees used to store a set of points in R^d can be made smooth and dynamic subject to insertions and deletions of points. The second version uses the first but must additionally deal with compression and alignment of quadtree components. In both cases our updates take 2^{O(d log d)} time, except for the point location part in the second version which has a lower bound of Omega(log n); but if a pointer (finger) to the correct quadtree cell is given, the rest of the updates take worst-case constant time. Our result implies that several classic and recent results (ranging from ray tracing to planar point location) in computational geometry which use quadtrees can deal with arbitrary point sets on a real RAM pointer machine.
Cite as
Ivor van der Hoog, Elena Khramtcova, and Maarten Löffler. Dynamic Smooth Compressed Quadtrees. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{vanderhoog_et_al:LIPIcs.SoCG.2018.45,
author = {van der Hoog, Ivor and Khramtcova, Elena and L\"{o}ffler, Maarten},
title = {{Dynamic Smooth Compressed Quadtrees}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {45:1--45:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.45},
URN = {urn:nbn:de:0030-drops-87581},
doi = {10.4230/LIPIcs.SoCG.2018.45},
annote = {Keywords: smooth, dynamic, data structure, quadtree, compression, alignment, Real RAM}
}
Document
On the Treewidth of Triangulated 3-Manifolds
Abstract
In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth.
In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs).
We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1)).
Cite as
Kristóf Huszár, Jonathan Spreer, and Uli Wagner. On the Treewidth of Triangulated 3-Manifolds. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{huszar_et_al:LIPIcs.SoCG.2018.46,
author = {Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan and Wagner, Uli},
title = {{On the Treewidth of Triangulated 3-Manifolds}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {46:1--46:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.46},
URN = {urn:nbn:de:0030-drops-87591},
doi = {10.4230/LIPIcs.SoCG.2018.46},
annote = {Keywords: computational topology, triangulations of 3-manifolds, thin position, fixed-parameter tractability, congestion, treewidth}
}
Document
On Partial Covering For Geometric Set Systems
Abstract
We study a generalization of the Set Cover problem called the Partial Set Cover in the context of geometric set systems. The input to this problem is a set system (X, R), where X is a set of elements and R is a collection of subsets of X, and an integer k <= |X|. Each set in R has a non-negative weight associated with it. The goal is to cover at least k elements of X by using a minimum-weight collection of sets from R. The main result of this article is an LP rounding scheme which shows that the integrality gap of the Partial Set Cover LP is at most a constant times that of the Set Cover LP for a certain projection of the set system (X, R). As a corollary of this result, we get improved approximation guarantees for the Partial Set Cover problem for a large class of geometric set systems.
Cite as
Tanmay Inamdar and Kasturi Varadarajan. On Partial Covering For Geometric Set Systems. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{inamdar_et_al:LIPIcs.SoCG.2018.47,
author = {Inamdar, Tanmay and Varadarajan, Kasturi},
title = {{On Partial Covering For Geometric Set Systems}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {47:1--47:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.47},
URN = {urn:nbn:de:0030-drops-87607},
doi = {10.4230/LIPIcs.SoCG.2018.47},
annote = {Keywords: Partial Set Cover, Geometric Set Cover}
}
Document
Optimality of Geometric Local Search
Abstract
Up until a decade ago, the algorithmic status of several basic çlass{NP}-complete problems in geometric combinatorial optimisation was unresolved. This included the existence of polynomial-time approximation schemes (PTASs) for hitting set, set cover, dominating set, independent set, and other problems for some basic geometric objects. These past nine years have seen the resolution of all these problems--interestingly, with the same algorithm: local search. In fact, it was shown that for many of these problems, local search with radius lambda gives a (1+O(lambda^{-1/2}))-approximation with running time n^{O(lambda)}. Setting lambda = Theta(epsilon^{-2}) yields a PTAS with a running time of n^{O(epsilon^{-2})}.
On the other hand, hardness results suggest that there do not exist PTASs for these problems with running time poly(n) * f(epsilon) for any arbitrary f. Thus the main question left open in previous work is in improving the exponent of n to o(epsilon^{-2}).
We show that in fact the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient, of independent interest, is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results. Our construction extends to other graph families with small separators.
Cite as
Bruno Jartoux and Nabil H. Mustafa. Optimality of Geometric Local Search. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{jartoux_et_al:LIPIcs.SoCG.2018.48,
author = {Jartoux, Bruno and Mustafa, Nabil H.},
title = {{Optimality of Geometric Local Search}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {48:1--48:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.48},
URN = {urn:nbn:de:0030-drops-87615},
doi = {10.4230/LIPIcs.SoCG.2018.48},
annote = {Keywords: local search, expansion, matchings, Hall's marriage theorem}
}
Document
Odd Yao-Yao Graphs are Not Spanners
Abstract
It is a long standing open problem whether Yao-Yao graphs YY_{k} are all spanners [Li et al. 2002]. Bauer and Damian [Bauer and Damian, 2012] showed that all YY_{6k} for k >= 6 are spanners. Li and Zhan [Li and Zhan, 2016] generalized their result and proved that all even Yao-Yao graphs YY_{2k} are spanners (for k >= 42). However, their technique cannot be extended to odd Yao-Yao graphs, and whether they are spanners are still elusive. In this paper, we show that, surprisingly, for any integer k >= 1, there exist odd Yao-Yao graph YY_{2k+1} instances, which are not spanners.
Cite as
Yifei Jin, Jian Li, and Wei Zhan. Odd Yao-Yao Graphs are Not Spanners. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{jin_et_al:LIPIcs.SoCG.2018.49,
author = {Jin, Yifei and Li, Jian and Zhan, Wei},
title = {{Odd Yao-Yao Graphs are Not Spanners}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {49:1--49:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.49},
URN = {urn:nbn:de:0030-drops-87621},
doi = {10.4230/LIPIcs.SoCG.2018.49},
annote = {Keywords: Odd Yao-Yao Graph, Spanner, Counterexample}
}
Document
Deletion in Abstract Voronoi Diagrams in Expected Linear Time
Abstract
Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem for a long time. Similarly for various concrete Voronoi diagrams of generalized sites, other than points. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion. We introduce the concept of a Voronoi-like diagram, a relaxed version of a Voronoi construct that has a structure similar to an abstract Voronoi diagram, without however being one. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under an insertion operation, thus, enabling its use in incremental constructions.
Cite as
Kolja Junginger and Evanthia Papadopoulou. Deletion in Abstract Voronoi Diagrams in Expected Linear Time. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{junginger_et_al:LIPIcs.SoCG.2018.50,
author = {Junginger, Kolja and Papadopoulou, Evanthia},
title = {{Deletion in Abstract Voronoi Diagrams in Expected Linear Time}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {50:1--50:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.50},
URN = {urn:nbn:de:0030-drops-87639},
doi = {10.4230/LIPIcs.SoCG.2018.50},
annote = {Keywords: Abstract Voronoi diagram, linear-time algorithm, update after deletion, randomized incremental algorithm}
}
Document
From a (p,2)-Theorem to a Tight (p,q)-Theorem
Abstract
A family F of sets is said to satisfy the (p,q)-property if among any p sets of F some q have a non-empty intersection. The celebrated (p,q)-theorem of Alon and Kleitman asserts that any family of compact convex sets in R^d that satisfies the (p,q)-property for some q >= d+1, can be pierced by a fixed number (independent on the size of the family) f_d(p,q) of points. The minimum such piercing number is denoted by {HD}_d(p,q). Already in 1957, Hadwiger and Debrunner showed that whenever q > (d-1)/d p+1 the piercing number is {HD}_d(p,q)=p-q+1; no exact values of {HD}_d(p,q) were found ever since.
While for an arbitrary family of compact convex sets in R^d, d >= 2, a (p,2)-property does not imply a bounded piercing number, such bounds were proved for numerous specific families. The best-studied among them is axis-parallel boxes in R^d, and specifically, axis-parallel rectangles in the plane. Wegner (1965) and (independently) Dol'nikov (1972) used a (p,2)-theorem for axis-parallel rectangles to show that {HD}_{rect}(p,q)=p-q+1 holds for all q>sqrt{2p}. These are the only values of q for which {HD}_{rect}(p,q) is known exactly.
In this paper we present a general method which allows using a (p,2)-theorem as a bootstrapping to obtain a tight (p,q)-theorem, for families with Helly number 2, even without assuming that the sets in the family are convex or compact. To demonstrate the strength of this method, we show that {HD}_{d-box}(p,q)=p-q+1 holds for all q > c' log^{d-1} p, and in particular, {HD}_{rect}(p,q)=p-q+1 holds for all q >= 7 log_2 p (compared to q >= sqrt{2p}, obtained by Wegner and Dol'nikov more than 40 years ago).
In addition, for several classes of families, we present improved (p,2)-theorems, some of which can be used as a bootstrapping to obtain tight (p,q)-theorems. In particular, we show that any family F of compact convex sets in R^d with Helly number 2 admits a (p,2)-theorem with piercing number O(p^{2d-1}), and thus, satisfies {HD}_{F}(p,q)=p-q+1 for all q>cp^{1-1/(2d-1)}, for a universal constant c.
Cite as
Chaya Keller and Shakhar Smorodinsky. From a (p,2)-Theorem to a Tight (p,q)-Theorem. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{keller_et_al:LIPIcs.SoCG.2018.51,
author = {Keller, Chaya and Smorodinsky, Shakhar},
title = {{From a (p,2)-Theorem to a Tight (p,q)-Theorem}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {51:1--51:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.51},
URN = {urn:nbn:de:0030-drops-87640},
doi = {10.4230/LIPIcs.SoCG.2018.51},
annote = {Keywords: (p,q)-Theorem, convexity, transversals, (p,2)-theorem, axis-parallel rectangles}
}
Document
Coloring Intersection Hypergraphs of Pseudo-Disks
Abstract
We prove that the intersection hypergraph of a family of n pseudo-disks with respect to another family of pseudo-disks admits a proper coloring with 4 colors and a conflict-free coloring with O(log n) colors. Along the way we prove that the respective Delaunay-graph is planar. We also prove that the intersection hypergraph of a family of n regions with linear union complexity with respect to a family of pseudo-disks admits a proper coloring with constantly many colors and a conflict-free coloring with O(log n) colors. Our results serve as a common generalization and strengthening of many earlier results, including ones about proper and conflict-free coloring points with respect to pseudo-disks, coloring regions of linear union complexity with respect to points and coloring disks with respect to disks.
Cite as
Balázs Keszegh. Coloring Intersection Hypergraphs of Pseudo-Disks. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{keszegh:LIPIcs.SoCG.2018.52,
author = {Keszegh, Bal\'{a}zs},
title = {{Coloring Intersection Hypergraphs of Pseudo-Disks}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {52:1--52:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.52},
URN = {urn:nbn:de:0030-drops-87657},
doi = {10.4230/LIPIcs.SoCG.2018.52},
annote = {Keywords: combinatorial geometry, conflict-free coloring, geometric hypergraph coloring}
}
Document
Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts
Abstract
Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one-page and two-page book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct half-planes (the pages) bounded by the spine. In this paper we study the problem of minimizing the crossings for a fixed cyclic vertex order by computing an optimal k-plane set of exteriorly drawn edges for k >= 1, extending the previously studied case k=0. We show that this relates to finding bounded-degree maximum-weight induced subgraphs of circle graphs, which is a graph-theoretic problem of independent interest. We show NP-hardness for arbitrary k, present an efficient algorithm for k=1, and generalize it to an explicit XP-time algorithm for any fixed k. For the practically interesting case k=1 we implemented our algorithm and present experimental results that confirm the applicability of our algorithm.
Cite as
Fabian Klute and Martin Nöllenburg. Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{klute_et_al:LIPIcs.SoCG.2018.53,
author = {Klute, Fabian and N\"{o}llenburg, Martin},
title = {{Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {53:1--53:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.53},
URN = {urn:nbn:de:0030-drops-87663},
doi = {10.4230/LIPIcs.SoCG.2018.53},
annote = {Keywords: Graph Drawing, Circular Layouts, Crossing Minimization, Circle Graphs, Bounded-Degree Maximum-Weight Induced Subgraphs}
}
Document
Discrete Stratified Morse Theory: A User's Guide
Abstract
Inspired by the works of Forman on discrete Morse theory, which is a combinatorial adaptation to cell complexes of classical Morse theory on manifolds, we introduce a discrete analogue of the stratified Morse theory of Goresky and MacPherson. We describe the basics of this theory and prove fundamental theorems relating the topology of a general simplicial complex with the critical simplices of a discrete stratified Morse function on the complex. We also provide an algorithm that constructs a discrete stratified Morse function out of an arbitrary function defined on a finite simplicial complex; this is different from simply constructing a discrete Morse function on such a complex. We borrow Forman's idea of a "user's guide," where we give simple examples to convey the utility of our theory.
Cite as
Kevin Knudson and Bei Wang. Discrete Stratified Morse Theory: A User's Guide. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{knudson_et_al:LIPIcs.SoCG.2018.54,
author = {Knudson, Kevin and Wang, Bei},
title = {{Discrete Stratified Morse Theory: A User's Guide}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {54:1--54:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.54},
URN = {urn:nbn:de:0030-drops-87671},
doi = {10.4230/LIPIcs.SoCG.2018.54},
annote = {Keywords: Discrete Morse theory, stratified Morse theory, topological data analysis}
}
Document
An Optimal Algorithm to Compute the Inverse Beacon Attraction Region
Abstract
The beacon model is a recent paradigm for guiding the trajectory of messages or small robotic agents in complex environments. A beacon is a fixed point with an attraction pull that can move points within a given polygon. Points move greedily towards a beacon: if unobstructed, they move along a straight line to the beacon, and otherwise they slide on the edges of the polygon. The Euclidean distance from a moving point to a beacon is monotonically decreasing. A given beacon attracts a point if the point eventually reaches the beacon.
The problem of attracting all points within a polygon with a set of beacons can be viewed as a variation of the art gallery problem. Unlike most variations, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. It is connected and can be computed in linear time for simple polygons. By contrast, it is known that the inverse attraction region of a point - the set of beacon positions that attract it - could have Omega(n) disjoint connected components.
In this paper, we prove that, in spite of this, the total complexity of the inverse attraction region of a point in a simple polygon is linear, and present a O(n log n) time algorithm to construct it. This improves upon the best previous algorithm which required O(n^3) time and O(n^2) space. Furthermore we prove a matching Omega(n log n) lower bound for this task in the algebraic computation tree model of computation, even if the polygon is monotone.
Cite as
Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman, and David Rappaport. An Optimal Algorithm to Compute the Inverse Beacon Attraction Region. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{kostitsyna_et_al:LIPIcs.SoCG.2018.55,
author = {Kostitsyna, Irina and Kouhestani, Bahram and Langerman, Stefan and Rappaport, David},
title = {{An Optimal Algorithm to Compute the Inverse Beacon Attraction Region}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {55:1--55:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.55},
URN = {urn:nbn:de:0030-drops-87686},
doi = {10.4230/LIPIcs.SoCG.2018.55},
annote = {Keywords: beacon attraction, inverse attraction region, algorithm, optimal}
}
Document
On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance
Abstract
We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given epsilon>0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most epsilon.
We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms perform compared to the optimum possible, also in the situation where the algorithms are given a considerably larger error threshold than epsilon. Furthermore, we show that computing an optimal simplification using the undirected Hausdorff distance is NP-hard. The same holds when using the directed Hausdorff distance from the input to the output polyline, whereas the reverse can be computed in polynomial time. Finally, to compute the optimal simplification from a polygonal line consisting of n vertices under the Fréchet distance, we give an O(kn^5) time algorithm that requires O(kn^2) space, where k is the output complexity of the simplification.
Cite as
Marc van Kreveld, Maarten Löffler, and Lionov Wiratma. On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{vankreveld_et_al:LIPIcs.SoCG.2018.56,
author = {van Kreveld, Marc and L\"{o}ffler, Maarten and Wiratma, Lionov},
title = {{On Optimal Polyline Simplification Using the Hausdorff and Fr\'{e}chet Distance}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {56:1--56:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.56},
URN = {urn:nbn:de:0030-drops-87694},
doi = {10.4230/LIPIcs.SoCG.2018.56},
annote = {Keywords: polygonal line simplification, Hausdorff distance, Fr\'{e}chet distance, Imai-Iri, Douglas-Peucker}
}
Document
Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors
Abstract
We take a first step towards a rigorous asymptotic analysis of graph-based methods for finding (approximate) nearest neighbors in high-dimensional spaces, by analyzing the complexity of randomized greedy walks on the approximate nearest neighbor graph. For random data sets of size n = 2^{o(d)} on the d-dimensional Euclidean unit sphere, using near neighbor graphs we can provably solve the approximate nearest neighbor problem with approximation factor c > 1 in query time n^{rho_{q} + o(1)} and space n^{1 + rho_{s} + o(1)}, for arbitrary rho_{q}, rho_{s} >= 0 satisfying (2c^2 - 1) rho_{q} + 2 c^2 (c^2 - 1) sqrt{rho_{s} (1 - rho_{s})} >= c^4. Graph-based near neighbor searching is especially competitive with hash-based methods for small c and near-linear memory, and in this regime the asymptotic scaling of a greedy graph-based search matches optimal hash-based trade-offs of Andoni-Laarhoven-Razenshteyn-Waingarten [Andoni et al., 2017]. We further study how the trade-offs scale when the data set is of size n = 2^{Theta(d)}, and analyze asymptotic complexities when applying these results to lattice sieving.
Cite as
Thijs Laarhoven. Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{laarhoven:LIPIcs.SoCG.2018.57,
author = {Laarhoven, Thijs},
title = {{Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {57:1--57:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.57},
URN = {urn:nbn:de:0030-drops-87700},
doi = {10.4230/LIPIcs.SoCG.2018.57},
annote = {Keywords: approximate nearest neighbor problem, near neighbor graphs, locality-sensitive hashing, locality-sensitive filters, similarity search}
}
Document
A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon
Abstract
The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is Omega(n+m log m), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve O((n+m)log (n+m)) and O(n+m log m log^2n) time, which are optimal for m=Omega(n) and m=O(n/(log^3n)), respectively. In this paper, we give a construction algorithm with O(n+m(log m+log^2 n)) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in O(log n) time, then the construction time will become the optimal O(n+m log m). In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in O(log n) time.
Cite as
Chih-Hung Liu. A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{liu:LIPIcs.SoCG.2018.58,
author = {Liu, Chih-Hung},
title = {{A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {58:1--58:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.58},
URN = {urn:nbn:de:0030-drops-87717},
doi = {10.4230/LIPIcs.SoCG.2018.58},
annote = {Keywords: Simple polygons, Voronoi diagrams, Geodesic distance}
}
Document
Further Consequences of the Colorful Helly Hypothesis
Abstract
Let F be a family of convex sets in R^d, which are colored with d+1 colors. We say that F satisfies the Colorful Helly Property if every rainbow selection of d+1 sets, one set from each color class, has a non-empty common intersection. The Colorful Helly Theorem of Lovász states that for any such colorful family F there is a color class F_i subset F, for 1 <= i <= d+1, whose sets have a non-empty intersection. We establish further consequences of the Colorful Helly hypothesis. In particular, we show that for each dimension d >= 2 there exist numbers f(d) and g(d) with the following property: either one can find an additional color class whose sets can be pierced by f(d) points, or all the sets in F can be crossed by g(d) lines.
Cite as
Leonardo Martínez-Sandoval, Edgardo Roldán-Pensado, and Natan Rubin. Further Consequences of the Colorful Helly Hypothesis. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{martinezsandoval_et_al:LIPIcs.SoCG.2018.59,
author = {Mart{\'\i}nez-Sandoval, Leonardo and Rold\'{a}n-Pensado, Edgardo and Rubin, Natan},
title = {{Further Consequences of the Colorful Helly Hypothesis}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {59:1--59:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.59},
URN = {urn:nbn:de:0030-drops-87726},
doi = {10.4230/LIPIcs.SoCG.2018.59},
annote = {Keywords: geometric transversals, convex sets, colorful Helly-type theorems, line transversals, weak epsilon-nets, transversal numbers}
}
Document
Random Walks on Polytopes of Constant Corank
Abstract
We show that the pivoting process associated with one line and n points in r-dimensional space may need Omega(log^r n) steps in expectation as n -> infty. The only cases for which the bound was known previously were for r <= 3. Our lower bound is also valid for the expected number of pivoting steps in the following applications: (1) The Random-Edge simplex algorithm on linear programs with n constraints in d = n-r variables; and (2) the directed random walk on a grid polytope of corank r with n facets.
Cite as
Malte Milatz. Random Walks on Polytopes of Constant Corank. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{milatz:LIPIcs.SoCG.2018.60,
author = {Milatz, Malte},
title = {{Random Walks on Polytopes of Constant Corank}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {60:1--60:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.60},
URN = {urn:nbn:de:0030-drops-87730},
doi = {10.4230/LIPIcs.SoCG.2018.60},
annote = {Keywords: polytope, unique sink orientation, grid, random walk}
}
Document
Table Based Detection of Degenerate Predicates in Free Space Construction
Abstract
The key to a robust and efficient implementation of a computational geometry algorithm is an efficient algorithm for detecting degenerate predicates. We study degeneracy detection in constructing the free space of a polyhedron that rotates around a fixed axis and translates freely relative to another polyhedron. The structure of the free space is determined by the signs of univariate polynomials, called angle polynomials, whose coefficients are polynomials in the coordinates of the vertices of the polyhedra. Every predicate is expressible as the sign of an angle polynomial f evaluated at a zero t of an angle polynomial g. A predicate is degenerate (the sign is zero) when t is a zero of a common factor of f and g. We present an efficient degeneracy detection algorithm based on a one-time factoring of every possible angle polynomial. Our algorithm is 3500 times faster than the standard algorithm based on greatest common divisor computation. It reduces the share of degeneracy detection in our free space computations from 90% to 0.5% of the running time.
Cite as
Victor Milenkovic, Elisha Sacks, and Nabeel Butt. Table Based Detection of Degenerate Predicates in Free Space Construction. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{milenkovic_et_al:LIPIcs.SoCG.2018.61,
author = {Milenkovic, Victor and Sacks, Elisha and Butt, Nabeel},
title = {{Table Based Detection of Degenerate Predicates in Free Space Construction}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {61:1--61:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.61},
URN = {urn:nbn:de:0030-drops-87749},
doi = {10.4230/LIPIcs.SoCG.2018.61},
annote = {Keywords: free space construction, degenerate predicates, robustness}
}
Document
Approximate Range Queries for Clustering
Abstract
We study the approximate range searching for three variants of the clustering problem with a set P of n points in d-dimensional Euclidean space and axis-parallel rectangular range queries: the k-median, k-means, and k-center range-clustering query problems. We present data structures and query algorithms that compute (1+epsilon)-approximations to the optimal clusterings of P cap Q efficiently for a query consisting of an orthogonal range Q, an integer k, and a value epsilon>0.
Cite as
Eunjin Oh and Hee-Kap Ahn. Approximate Range Queries for Clustering. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{oh_et_al:LIPIcs.SoCG.2018.62,
author = {Oh, Eunjin and Ahn, Hee-Kap},
title = {{Approximate Range Queries for Clustering}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {62:1--62:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.62},
URN = {urn:nbn:de:0030-drops-87755},
doi = {10.4230/LIPIcs.SoCG.2018.62},
annote = {Keywords: Approximate clustering, orthogonal range queries}
}
Document
Point Location in Dynamic Planar Subdivisions
Abstract
We study the point location problem on dynamic planar subdivisions that allows insertions and deletions of edges. In our problem, the underlying graph of a subdivision is not necessarily connected. We present a data structure of linear size for such a dynamic planar subdivision that supports sublinear-time update and polylogarithmic-time query. Precisely, the amortized update time is O(sqrt{n}log n(log log n)^{3/2}) and the query time is O(log n(log log n)^2), where n is the number of edges in the subdivision. This answers a question posed by Snoeyink in the Handbook of Computational Geometry. When only deletions of edges are allowed, the update time and query time are just O(alpha(n)) and O(log n), respectively.
Cite as
Eunjin Oh and Hee-Kap Ahn. Point Location in Dynamic Planar Subdivisions. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{oh_et_al:LIPIcs.SoCG.2018.63,
author = {Oh, Eunjin and Ahn, Hee-Kap},
title = {{Point Location in Dynamic Planar Subdivisions}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {63:1--63:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.63},
URN = {urn:nbn:de:0030-drops-87769},
doi = {10.4230/LIPIcs.SoCG.2018.63},
annote = {Keywords: dynamic point location, general subdivision}
}
Document
Edge-Unfolding Nearly Flat Convex Caps
Abstract
The main result of this paper is a proof that a nearly flat, acutely triangulated convex cap C in R^3 has an edge-unfolding to a non-overlapping polygon in the plane. A convex cap is the intersection of the surface of a convex polyhedron and a halfspace. "Nearly flat" means that every outer face normal forms a sufficiently small angle f < F with the z^-axis orthogonal to the halfspace bounding plane. The size of F depends on the acuteness gap a: if every triangle angle is at most pi/2 {-} a, then F ~~ 0.36 sqrt{a} suffices; e.g., for a=3°, F ~~ 5°. The proof employs the recent concepts of angle-monotone and radially monotone curves. The proof is constructive, leading to a polynomial-time algorithm for finding the edge-cuts, at worst O(n^2); a version has been implemented.
Cite as
Joseph O'Rourke. Edge-Unfolding Nearly Flat Convex Caps. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{orourke:LIPIcs.SoCG.2018.64,
author = {O'Rourke, Joseph},
title = {{Edge-Unfolding Nearly Flat Convex Caps}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {64:1--64:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.64},
URN = {urn:nbn:de:0030-drops-87777},
doi = {10.4230/LIPIcs.SoCG.2018.64},
annote = {Keywords: polyhedra, unfolding}
}
Document
A Crossing Lemma for Multigraphs
Abstract
Let G be a drawing of a graph with n vertices and e>4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, the number of crossings in G is at least c{e^3 over n^2}, for a suitable constant c>0. In a seminal paper, Székely generalized this result to multigraphs, establishing the lower bound c{e^3 over mn^2}, where m denotes the maximum multiplicity of an edge in G. We get rid of the dependence on m by showing that, as in the original Crossing Lemma, the number of crossings is at least c'{e^3 over n^2} for some c'>0, provided that the "lens" enclosed by every pair of parallel edges in G contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou.
Cite as
János Pach and Géza Tóth. A Crossing Lemma for Multigraphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{pach_et_al:LIPIcs.SoCG.2018.65,
author = {Pach, J\'{a}nos and T\'{o}th, G\'{e}za},
title = {{A Crossing Lemma for Multigraphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {65:1--65:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.65},
URN = {urn:nbn:de:0030-drops-87781},
doi = {10.4230/LIPIcs.SoCG.2018.65},
annote = {Keywords: crossing number, Crossing Lemma, multigraph, separator theorem}
}
Document
Near-Optimal Coresets of Kernel Density Estimates
Abstract
We construct near-optimal coresets for kernel density estimate for points in R^d when the kernel is positive definite. Specifically we show a polynomial time construction for a coreset of size O(sqrt{d log (1/epsilon)}/epsilon), and we show a near-matching lower bound of size Omega(sqrt{d}/epsilon). The upper bound is a polynomial in 1/epsilon improvement when d in [3,1/epsilon^2) (for all kernels except the Gaussian kernel which had a previous upper bound of O((1/epsilon) log^d (1/epsilon))) and the lower bound is the first known lower bound to depend on d for this problem. Moreover, the upper bound restriction that the kernel is positive definite is significant in that it applies to a wide-variety of kernels, specifically those most important for machine learning. This includes kernels for information distances and the sinc kernel which can be negative.
Cite as
Jeff M. Phillips and Wai Ming Tai. Near-Optimal Coresets of Kernel Density Estimates. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 66:1-66:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{phillips_et_al:LIPIcs.SoCG.2018.66,
author = {Phillips, Jeff M. and Tai, Wai Ming},
title = {{Near-Optimal Coresets of Kernel Density Estimates}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {66:1--66:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.66},
URN = {urn:nbn:de:0030-drops-87797},
doi = {10.4230/LIPIcs.SoCG.2018.66},
annote = {Keywords: Coresets, Kernel Density Estimate, Discrepancy}
}
Document
Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line
Abstract
In the online metric bipartite matching problem, we are given a set S of server locations in a metric space. Requests arrive one at a time, and on its arrival, we need to immediately and irrevocably match it to a server at a cost which is equal to the distance between these locations. A alpha-competitive algorithm will assign requests to servers so that the total cost is at most alpha times the cost of M_{Opt} where M_{Opt} is the minimum cost matching between S and R.
We consider this problem in the adversarial model for the case where S and R are points on a line and |S|=|R|=n. We improve the analysis of the deterministic Robust Matching Algorithm (RM-Algorithm, Nayyar and Raghvendra FOCS'17) from O(log^2 n) to an optimal Theta(log n). Previously, only a randomized algorithm under a weaker oblivious adversary achieved a competitive ratio of O(log n) (Gupta and Lewi, ICALP'12). The well-known Work Function Algorithm (WFA) has a competitive ratio of O(n) and Omega(log n) for this problem. Therefore, WFA cannot achieve an asymptotically better competitive ratio than the RM-Algorithm.
Cite as
Sharath Raghvendra. Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{raghvendra:LIPIcs.SoCG.2018.67,
author = {Raghvendra, Sharath},
title = {{Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {67:1--67:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.67},
URN = {urn:nbn:de:0030-drops-87803},
doi = {10.4230/LIPIcs.SoCG.2018.67},
annote = {Keywords: Bipartite Matching, Online Algorithms, Adversarial Model, Line Metric}
}
Document
Almost All String Graphs are Intersection Graphs of Plane Convex Sets
Abstract
A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge (n --> infty). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets.
Cite as
János Pach, Bruce Reed, and Yelena Yuditsky. Almost All String Graphs are Intersection Graphs of Plane Convex Sets. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{pach_et_al:LIPIcs.SoCG.2018.68,
author = {Pach, J\'{a}nos and Reed, Bruce and Yuditsky, Yelena},
title = {{Almost All String Graphs are Intersection Graphs of Plane Convex Sets}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {68:1--68:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.68},
URN = {urn:nbn:de:0030-drops-87818},
doi = {10.4230/LIPIcs.SoCG.2018.68},
annote = {Keywords: String graph, intersection graph, plane convex set}
}
Document
An Improved Bound for the Size of the Set A/A+A
Abstract
It is established that for any finite set of positive real numbers A, we have |A/A+A| >> |A|^{3/2+1/26} / log^{5/6}|A|.
Cite as
Oliver Roche-Newton. An Improved Bound for the Size of the Set A/A+A. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 69:1-69:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{rochenewton:LIPIcs.SoCG.2018.69,
author = {Roche-Newton, Oliver},
title = {{An Improved Bound for the Size of the Set A/A+A}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {69:1--69:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.69},
URN = {urn:nbn:de:0030-drops-87820},
doi = {10.4230/LIPIcs.SoCG.2018.69},
annote = {Keywords: sum-product estimates, expanders, incidence theorems, discrete geometry}
}
Document
Fractal Dimension and Lower Bounds for Geometric Problems
Abstract
We study the complexity of geometric problems on spaces of low fractal dimension. It was recently shown by [Sidiropoulos & Sridhar, SoCG 2017] that several problems admit improved solutions when the input is a pointset in Euclidean space with fractal dimension smaller than the ambient dimension. In this paper we prove nearly-matching lower bounds, thus establishing nearly-optimal bounds for various problems as a function of the fractal dimension.
More specifically, we show that for any set of n points in d-dimensional Euclidean space, of fractal dimension delta in (1,d), for any epsilon>0 and c >= 1, any c-spanner must have treewidth at least Omega(n^{1-1/(delta - epsilon)} / c^{d-1}), matching the previous upper bound. The construction used to prove this lower bound on the treewidth of spanners, can also be used to derive lower bounds on the running time of algorithms for various problems, assuming the Exponential Time Hypothesis. We provide two prototypical results of this type:
- For any delta in (1,d) and any epsilon >0, d-dimensional Euclidean TSP on n points with fractal dimension at most delta cannot be solved in time 2^{O(n^{1-1/(delta - epsilon)})}. The best-known upper bound is 2^{O(n^{1-1/delta} log n)}.
- For any delta in (1,d) and any epsilon >0, the problem of finding k-pairwise non-intersecting d-dimensional unit balls/axis parallel unit cubes with centers having fractal dimension at most delta cannot be solved in time f(k)n^{O (k^{1-1/(delta - epsilon)})} for any computable function f. The best-known upper bound is n^{O(k^{1-1/delta} log n)}. The above results nearly match previously known upper bounds from [Sidiropoulos & Sridhar, SoCG 2017], and generalize analogous lower bounds for the case of ambient dimension due to [Marx & Sidiropoulos, SoCG 2014].
Cite as
Anastasios Sidiropoulos, Kritika Singhal, and Vijay Sridhar. Fractal Dimension and Lower Bounds for Geometric Problems. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{sidiropoulos_et_al:LIPIcs.SoCG.2018.70,
author = {Sidiropoulos, Anastasios and Singhal, Kritika and Sridhar, Vijay},
title = {{Fractal Dimension and Lower Bounds for Geometric Problems}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {70:1--70:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.70},
URN = {urn:nbn:de:0030-drops-87831},
doi = {10.4230/LIPIcs.SoCG.2018.70},
annote = {Keywords: fractal dimension, treewidth, spanners, lower bounds, exponential time hypothesis}
}
Document
The Trisection Genus of Standard Simply Connected PL 4-Manifolds
Abstract
Gay and Kirby recently introduced the concept of a trisection for arbitrary smooth, oriented closed 4-manifolds, and with it a new topological invariant, called the trisection genus. In this note we show that the K3 surface has trisection genus 22. This implies that the trisection genus of all standard simply connected PL 4-manifolds is known. We show that the trisection genus of each of these manifolds is realised by a trisection that is supported by a singular triangulation. Moreover, we explicitly give the building blocks to construct these triangulations.
Cite as
Jonathan Spreer and Stephan Tillmann. The Trisection Genus of Standard Simply Connected PL 4-Manifolds. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 71:1-71:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{spreer_et_al:LIPIcs.SoCG.2018.71,
author = {Spreer, Jonathan and Tillmann, Stephan},
title = {{The Trisection Genus of Standard Simply Connected PL 4-Manifolds}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {71:1--71:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.71},
URN = {urn:nbn:de:0030-drops-87847},
doi = {10.4230/LIPIcs.SoCG.2018.71},
annote = {Keywords: combinatorial topology, triangulated manifolds, simply connected 4-manifolds, K3 surface, trisections of 4-manifolds}
}
Document
An O(n log n)-Time Algorithm for the k-Center Problem in Trees
Abstract
We consider a classical k-center problem in trees. Let T be a tree of n vertices and every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such that the maximum weighted distance from all vertices to their closest centers is minimized. Megiddo and Tamir (SIAM J. Comput., 1983) gave an algorithm that can solve the problem in O(n log^2 n) time by using Cole's parametric search. Since then it has been open for over three decades whether the problem can be solved in O(n log n) time. In this paper, we present an O(n log n) time algorithm for the problem and thus settle the open problem affirmatively.
Cite as
Haitao Wang and Jingru Zhang. An O(n log n)-Time Algorithm for the k-Center Problem in Trees. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{wang_et_al:LIPIcs.SoCG.2018.72,
author = {Wang, Haitao and Zhang, Jingru},
title = {{An O(n log n)-Time Algorithm for the k-Center Problem in Trees}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {72:1--72:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.72},
URN = {urn:nbn:de:0030-drops-87852},
doi = {10.4230/LIPIcs.SoCG.2018.72},
annote = {Keywords: k-center, trees, facility locations}
}
Document
New Bounds for Range Closest-Pair Problems
Abstract
Given a dataset S of points in R^2, the range closest-pair (RCP) problem aims to preprocess S into a data structure such that when a query range X is specified, the closest-pair in S cap X can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional range-search problems. This paper revisits the RCP problem, and proposes new data structures for various query types including quadrants, strips, rectangles, and halfplanes. Both worst-case and average-case analyses (in the sense that the data points are drawn uniformly and independently from the unit square) are applied to these new data structures, which result in new bounds for the RCP problem. Some of the new bounds significantly improve the previous results, while the others are entirely new.
Cite as
Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan. New Bounds for Range Closest-Pair Problems. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{xue_et_al:LIPIcs.SoCG.2018.73,
author = {Xue, Jie and Li, Yuan and Rahul, Saladi and Janardan, Ravi},
title = {{New Bounds for Range Closest-Pair Problems}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {73:1--73:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.73},
URN = {urn:nbn:de:0030-drops-87865},
doi = {10.4230/LIPIcs.SoCG.2018.73},
annote = {Keywords: Closest-pair, Range search, Candidate pairs, Average-case analysis}
}
Document
Multimedia Exposition
Coordinated Motion Planning: The Video (Multimedia Exposition)
Abstract
We motivate, visualize and demonstrate recent work for minimizing the total execution time of a coordinated, parallel motion plan for a swarm of N robots in the absence of obstacles. Under relatively mild assumptions on the separability of robots, the algorithm achieves constant stretch: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot) is O(d) steps; this implies constant-factor approximation for the optimization problem. Also mentioned is an NP-hardness result for finding an optimal schedule, even in the case in which robot positions are restricted to a regular grid. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) is required in the worst case; we establish an achievable stretch factor of O(N^{1/2}) even in this case. We also sketch geometric difficulties of computing optimal trajectories, even for just two unit disks.
Cite as
Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, and Christian Scheffer. Coordinated Motion Planning: The Video (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 74:1-74:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{becker_et_al:LIPIcs.SoCG.2018.74,
author = {Becker, Aaron T. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Konitzny, Matthias and Lin, Lillian and Scheffer, Christian},
title = {{Coordinated Motion Planning: The Video}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {74:1--74:6},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.74},
URN = {urn:nbn:de:0030-drops-87872},
doi = {10.4230/LIPIcs.SoCG.2018.74},
annote = {Keywords: Motion planning, robot swarms, complexity, stretch, approximation}
}
Document
Multimedia Exposition
Geometric Realizations of the 3D Associahedron (Multimedia Exposition)
Abstract
The associahedron is a convex polytope whose 1-skeleton is isomorphic to the flip graph of a convex polygon. There exists an elegant geometric realization of the associahedron, using the remarkable theory of secondary polytopes, based on the geometry of the underlying polygon. We present an interactive application that visualizes this correspondence in the 3D case.
Cite as
Satyan L. Devadoss, Daniel D. Johnson, Justin Lee, and Jackson Warley. Geometric Realizations of the 3D Associahedron (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 75:1-75:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{devadoss_et_al:LIPIcs.SoCG.2018.75,
author = {Devadoss, Satyan L. and Johnson, Daniel D. and Lee, Justin and Warley, Jackson},
title = {{Geometric Realizations of the 3D Associahedron}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {75:1--75:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.75},
URN = {urn:nbn:de:0030-drops-87886},
doi = {10.4230/LIPIcs.SoCG.2018.75},
annote = {Keywords: associahedron, secondary polytope, realization}
}
Document
Multimedia Exposition
Star Unfolding of Boxes (Multimedia Exposition)
Abstract
Given a convex polyhedron, the star unfolding of its surface is obtained by cutting along the shortest paths from a fixed source point to each of its vertices. We present an interactive application that visualizes the star unfolding of a box, such that its dimensions and source point locations can be continuously toggled by the user.
Cite as
Dani Demas, Satyan L. Devadoss, and Yu Xuan Hong. Star Unfolding of Boxes (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 76:1-76:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{demas_et_al:LIPIcs.SoCG.2018.76,
author = {Demas, Dani and Devadoss, Satyan L. and Hong, Yu Xuan},
title = {{Star Unfolding of Boxes}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {76:1--76:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.76},
URN = {urn:nbn:de:0030-drops-87890},
doi = {10.4230/LIPIcs.SoCG.2018.76},
annote = {Keywords: star unfolding, source unfolding, Voronoi diagram}
}
Document
Multimedia Exposition
VoroCrust Illustrated: Theory and Challenges (Multimedia Exposition)
Abstract
Over the past decade, polyhedral meshing has been gaining popularity as a better alternative to tetrahedral meshing in certain applications. Within the class of polyhedral elements, Voronoi cells are particularly attractive thanks to their special geometric structure. What has been missing so far is a Voronoi mesher that is sufficiently robust to run automatically on complex models. In this video, we illustrate the main ideas behind the VoroCrust algorithm, highlighting both the theoretical guarantees and the practical challenges imposed by realistic inputs.
Cite as
Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, and Ahmad A. Rushdi. VoroCrust Illustrated: Theory and Challenges (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 77:1-77:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{abdelkader_et_al:LIPIcs.SoCG.2018.77,
author = {Abdelkader, Ahmed and Bajaj, Chandrajit L. and Ebeida, Mohamed S. and Mahmoud, Ahmed H. and Mitchell, Scott A. and Owens, John D. and Rushdi, Ahmad A.},
title = {{VoroCrust Illustrated: Theory and Challenges}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {77:1--77:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Speckmann, Bettina and T\'{o}th, Csaba D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.77},
URN = {urn:nbn:de:0030-drops-87903},
doi = {10.4230/LIPIcs.SoCG.2018.77},
annote = {Keywords: sampling, surface reconstruction, polyhedral meshing, Voronoi}
}