Volume
LIPIcs, Volume 51
32nd International Symposium on Computational Geometry (SoCG 2016)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG)
Event
SoCG 2016, June 14-18, 2016, Boston, USAEditors
Publication Details
- published at: 2016-06-10
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-009-5
- DBLP: db/conf/compgeom/compgeom2016
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 51, SoCG'16, Complete Volume
Abstract
LIPIcs, Volume 51, SoCG'16, Complete Volume
Cite as
32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@Proceedings{fekete_et_al:LIPIcs.SoCG.2016,
title = {{LIPIcs, Volume 51, SoCG'16, Complete Volume}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016},
URN = {urn:nbn:de:0030-drops-60580},
doi = {10.4230/LIPIcs.SoCG.2016},
annote = {Keywords: Analysis of Algorithms and Problem Complexity, Nonnumerical Algorithms and Problems – Geometrical problems and computations, Discrete Mathematics, Combinatorics, Computer Graphics, Computational Geometry and Object Modeling}
}
Document
Front Matter
Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors
Abstract
Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors
Cite as
32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{fekete_et_al:LIPIcs.SoCG.2016.0,
author = {Fekete, S\'{a}ndor and Lubiw, Anna},
title = {{Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {0:i--0:xviii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.0},
URN = {urn:nbn:de:0030-drops-59658},
doi = {10.4230/LIPIcs.SoCG.2016.0},
annote = {Keywords: Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors}
}
Document
Invited Talk
Toward Pervasive Robots (Invited Talk)
Abstract
The digitization of practically everything coupled with the mobile Internet, the automation of knowledge work, and advanced robotics promises a future with democratized use of machines and wide-spread use of robots and customization. However, pervasive use of robots remains a hard problem. Where are the gaps that we need to address in order to advance toward a future where robots are common in the world and they help reliably with physical tasks? What is the role of geometric reasoning along this trajectory?
In this talk I will discuss challenges toward pervasive use of robots and recent developments in geometric algorithms for customizing robots. I will focus on a suite of gemetric algorithms for automatically designing, fabricating, and tasking robots using a print-and-fold approach. I will also describe how geometric reasoning can play a role in creating robots more capable of reasoning in the world. By enabling on-demand creation of programmable robots, we can begin to imagine a world with one robot for every physical task.
Cite as
Daniela Rus. Toward Pervasive Robots (Invited Talk). In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{rus:LIPIcs.SoCG.2016.1,
author = {Rus, Daniela},
title = {{Toward Pervasive Robots}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.1},
URN = {urn:nbn:de:0030-drops-58939},
doi = {10.4230/LIPIcs.SoCG.2016.1},
annote = {Keywords: rus@csail.mit.edu}
}
Document
Invited Talk
Discrete Geometry, Algebra, and Combinatorics (Invited Talk)
Abstract
Many problems in discrete and computational geometry can be viewed as finding patterns in graphs or hypergraphs which arise from geometry or algebra. Famous Ramsey, Turán, and Szemerédi-type results prove the existence of certain patterns in graphs and hypergraphs under mild assumptions. We survey recent results which show much stronger/larger patterns for graphs and hypergraphs that arise from geometry or algebra. We further discuss whether the stronger results in these settings are due to geometric, algebraic, combinatorial, or topological properties of the graphs.
Cite as
Jacob Fox. Discrete Geometry, Algebra, and Combinatorics (Invited Talk). In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{fox:LIPIcs.SoCG.2016.2,
author = {Fox, Jacob},
title = {{Discrete Geometry, Algebra, and Combinatorics}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {2:1--2:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.2},
URN = {urn:nbn:de:0030-drops-58948},
doi = {10.4230/LIPIcs.SoCG.2016.2},
annote = {Keywords: discrete geometry, extremal combinatorics, regularity lemmas, Ramsey theory}
}
Document
Who Needs Crossings? Hardness of Plane Graph Rigidity
Abstract
We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: "globally noncrossing" graphs, which avoid crossings in all of their configurations; matchstick graphs, with unit-length edges and where only noncrossing configurations are considered; and unrestricted graphs (crossings allowed) with unit edge lengths (or in the global rigidity case, edge lengths in {1,2}). We show that all nine of these questions are complete for the class Exists-R, defined by the Existential Theory of the Reals, or its complement Forall-R; in particular, each problem is (co)NP-hard.
One of these nine results - that realization of unit-distance graphs is Exists-R-complete - was shown previously by Schaefer (2013), but the other eight are new. We strengthen several prior results. Matchstick graph realization was known to be NP-hard (Eades & Wormald 1990, or Cabello et al. 2007), but its membership in NP remained open; we show it is complete for the (possibly) larger class Exists-R. Global rigidity of graphs with edge lengths in {1,2} was known to be coNP-hard (Saxe 1979); we show it is Forall-R-complete.
The majority of the paper is devoted to proving an analog of Kempe's Universality Theorem - informally, "there is a linkage to sign your name" - for globally noncrossing linkages. In particular, we show that any polynomial curve phi(x,y)=0 can be traced by a noncrossing linkage, settling an open problem from 2004. More generally, we show that the nontrivial regions in the plane that may be traced by a noncrossing linkage are precisely the compact semialgebraic regions. Thus, no drawing power is lost by restricting to noncrossing linkages. We prove analogous results for matchstick linkages and unit-distance linkages as well.
Cite as
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl. Who Needs Crossings? Hardness of Plane Graph Rigidity. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{abel_et_al:LIPIcs.SoCG.2016.3,
author = {Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lynch, Jayson and Schardl, Tao B.},
title = {{Who Needs Crossings? Hardness of Plane Graph Rigidity}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {3:1--3:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.3},
URN = {urn:nbn:de:0030-drops-58951},
doi = {10.4230/LIPIcs.SoCG.2016.3},
annote = {Keywords: Graph Drawing, Graph Rigidity Theory, Graph Global Rigidity, Linkages, Complexity Theory, Computational Geometry}
}
Document
Finding the Maximum Subset with Bounded Convex Curvature
Abstract
We describe an algorithm for solving an important geometric problem arising in computer-aided manufacturing. When machining a pocket in a solid piece of material such as steel using a rough tool in a milling machine, sharp convex corners of the pocket cannot be done properly, but have to be left for finer tools that are more expensive to use. We want to determine a tool path that maximizes the use of the rough tool. Mathematically, this boils down to the following problem. Given a simply-connected set of points P in the plane such that the boundary of P is a curvilinear polygon consisting of n line segments and circular arcs of arbitrary radii, compute the maximum subset Q of P consisting of simply-connected sets where the boundary of each set is a curve with bounded convex curvature. A closed curve has bounded convex curvature if, when traversed in counterclockwise direction, it turns to the left with curvature at most 1. There is no bound on the curvature where it turns to the right. The difference in the requirement to left- and right-curvature is a natural consequence of different conditions when machining convex and concave areas of the pocket. We devise an algorithm to compute the unique maximum such set Q. The algorithm runs in O(n log n) time and uses O(n) space.
For the correctness of our algorithm, we prove a new generalization of the Pestov-Ionin Theorem. This is needed to show that the output Q of our algorithm is indeed maximum in the sense that if Q' is any subset of P with a boundary of bounded convex curvature, then Q' is a subset of Q.
Cite as
Mikkel Abrahamsen and Mikkel Thorup. Finding the Maximum Subset with Bounded Convex Curvature. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2016.4,
author = {Abrahamsen, Mikkel and Thorup, Mikkel},
title = {{Finding the Maximum Subset with Bounded Convex Curvature}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {4:1--4:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.4},
URN = {urn:nbn:de:0030-drops-58960},
doi = {10.4230/LIPIcs.SoCG.2016.4},
annote = {Keywords: planar computational geometry, bounded curvature, pocket machining}
}
Document
Coloring Points with Respect to Squares
Abstract
We consider the problem of 2-coloring geometric hypergraphs. Specifically, we show that there is a constant m such that any finite set S of points in the plane can be 2-colored such that every axis-parallel square that contains at least m points from S contains points of both colors. Our proof is constructive, that is, it provides a polynomial-time algorithm for obtaining such a 2-coloring. By affine transformations this result immediately applies also when considering homothets of a fixed parallelogram.
Cite as
Eyal Ackerman, Balázs Keszegh, and Máté Vizer. Coloring Points with Respect to Squares. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{ackerman_et_al:LIPIcs.SoCG.2016.5,
author = {Ackerman, Eyal and Keszegh, Bal\'{a}zs and Vizer, M\'{a}t\'{e}},
title = {{Coloring Points with Respect to Squares}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {5:1--5:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.5},
URN = {urn:nbn:de:0030-drops-58972},
doi = {10.4230/LIPIcs.SoCG.2016.5},
annote = {Keywords: Geometric hypergraph coloring, Polychromatic coloring, Homothets, Cover-decomposability}
}
Document
Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences
Abstract
We present the first subquadratic algorithms for computing similarity between a pair of point sequences in R^d, for any fixed d > 1, using dynamic time warping (DTW) and edit distance, assuming that the point sequences are drawn from certain natural families of curves. In particular, our algorithms compute (1 + eps)-approximations of DTW and ED in near-linear time for point sequences drawn from k-packed or k-bounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is k-packed if the length of its intersection with any ball of radius r is at most kr, and it is k-bounded if the sub-curve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for d = 1.
The commonly used dynamic programming algorithms for these distance measures reduce the problem to computing a minimum-weight path in a grid graph. Our algorithms work by constructing a small set of rectangular regions that cover the grid vertices. The weights of vertices inside each rectangle are roughly the same, and we develop efficient procedures to compute the approximate minimum-weight paths through these rectangles.
Cite as
Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2016.6,
author = {Agarwal, Pankaj K. and Fox, Kyle and Pan, Jiangwei and Ying, Rex},
title = {{Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {6:1--6:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.6},
URN = {urn:nbn:de:0030-drops-58989},
doi = {10.4230/LIPIcs.SoCG.2016.6},
annote = {Keywords: Dynamic time warping, Edit distance, Near-linear-time algorithm, Dynamic programming, Well-separated pair decomposition}
}
Document
An Improved Lower Bound on the Minimum Number of Triangulations
Abstract
Upper and lower bounds for the number of geometric graphs of specific types on a given set of points in the plane have been intensively studied in recent years. For most classes of geometric graphs it is now known that point sets in convex position minimize their number. However, it is still unclear which point sets minimize the number of geometric triangulations; the so-called double circles are conjectured to be the minimizing sets. In this paper we prove that any set of n points in general position in the plane has at least Omega(2.631^n) geometric triangulations. Our result improves the previously best general lower bound of Omega(2.43^n) and also covers the previously best lower bound of Omega(2.63^n) for a fixed number of extreme points. We achieve our bound by showing and combining several new results, which are of independent interest:
(1) Adding a point on the second convex layer of a given point set (of 7 or more points) at least doubles the number of triangulations.
(2) Generalized configurations of points that minimize the number of triangulations have at most n/2 points on their convex hull.
(3) We provide tight lower bounds for the number of triangulations of point sets with up to 15 points. These bounds further support the double circle conjecture.
Cite as
Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber. An Improved Lower Bound on the Minimum Number of Triangulations. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2016.7,
author = {Aichholzer, Oswin and Alvarez, Victor and Hackl, Thomas and Pilz, Alexander and Speckmann, Bettina and Vogtenhuber, Birgit},
title = {{An Improved Lower Bound on the Minimum Number of Triangulations}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {7:1--7:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.7},
URN = {urn:nbn:de:0030-drops-58993},
doi = {10.4230/LIPIcs.SoCG.2016.7},
annote = {Keywords: Combinatorial geometry, Order types, Triangulations}
}
Document
Recognizing Weakly Simple Polygons
Abstract
We present an O(n log n)-time algorithm that determines whether a given planar n-gon is weakly simple. This improves upon an O(n^2 log n)-time algorithm by [Chang, Erickson, and Xu, SODA, 2015]. Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question.
Cite as
Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba Tóth. Recognizing Weakly Simple Polygons. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{akitaya_et_al:LIPIcs.SoCG.2016.8,
author = {Akitaya, Hugo A. and Aloupis, Greg and Erickson, Jeff and T\'{o}th, Csaba},
title = {{Recognizing Weakly Simple Polygons}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {8:1--8:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.8},
URN = {urn:nbn:de:0030-drops-59003},
doi = {10.4230/LIPIcs.SoCG.2016.8},
annote = {Keywords: weakly simple polygon, crossing}
}
Document
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing
Abstract
We prove a tight lower bound for the exponent rho for data-dependent Locality-Sensitive Hashing schemes, recently used to
design efficient solutions for the c-approximate nearest neighbor search. In particular, our lower bound matches the bound of rho<= 1/(2c-1)+o(1) for the l_1 space, obtained via the recent algorithm from [Andoni-Razenshteyn, STOC'15].
In recent years it emerged that data-dependent hashing is strictly superior to the classical Locality-Sensitive Hashing, when
the hash function is data-independent. In the latter setting, the best exponent has been already known: for the l_1 space, the tight bound is rho=1/c, with the upper bound from [Indyk-Motwani,STOC'98] and the matching lower bound from [O'Donnell-Wu-Zhou,ITCS'11].
We prove that, even if the hashing is data-dependent, it must hold that rho>=1/(2c-1)-o(1). To prove the result, we need to
formalize the exact notion of data-dependent hashing that also captures the complexity of the hash functions (in addition to their collision properties). Without restricting such complexity, we would allow for obviously infeasible solutions such as the Voronoi diagram of a dataset. To preclude such solutions, we require our hash functions to be succinct. This condition is satisfied by all the known algorithmic results.
Cite as
Alexandr Andoni and Ilya Razensteyn. Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{andoni_et_al:LIPIcs.SoCG.2016.9,
author = {Andoni, Alexandr and Razensteyn, Ilya},
title = {{Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {9:1--9:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.9},
URN = {urn:nbn:de:0030-drops-59014},
doi = {10.4230/LIPIcs.SoCG.2016.9},
annote = {Keywords: similarity search, high-dimensional geometry, LSH, data structures, lower bounds}
}
Document
The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions
Abstract
We show that the union of translates of a convex body in three dimensional space can have a cubic number holes in the worst case, where a hole in a set is a connected component of its compliment. This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.
Cite as
Boris Aronov, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc. The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{aronov_et_al:LIPIcs.SoCG.2016.10,
author = {Aronov, Boris and Cheong, Otfried and Dobbins, Michael Gene and Goaoc, Xavier},
title = {{The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {10:1--10:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.10},
URN = {urn:nbn:de:0030-drops-59024},
doi = {10.4230/LIPIcs.SoCG.2016.10},
annote = {Keywords: Union complexity, Convex sets, Motion planning}
}
Document
On the Combinatorial Complexity of Approximating Polytopes
Abstract
Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter $diam(K)$ is given in Euclidean d-dimensional space, where $d$ is a constant. Given an error parameter eps > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most eps diam(K). By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that O(1/eps^{(d-1)/2}) facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is O-tilde(1/eps^{(d-1)/2}), where O-tilde conceals a polylogarithmic factor in 1/eps. This is an improvement upon the best known bound, which is roughly O(1/eps^{d-2}).
Our result is based on a novel combination of both new and old ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Barany and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.
Cite as
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. On the Combinatorial Complexity of Approximating Polytopes. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{arya_et_al:LIPIcs.SoCG.2016.11,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
title = {{On the Combinatorial Complexity of Approximating Polytopes}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.11},
URN = {urn:nbn:de:0030-drops-59034},
doi = {10.4230/LIPIcs.SoCG.2016.11},
annote = {Keywords: Polytope approximation, Convex polytopes, Macbeath regions}
}
Document
Efficient Algorithms to Decide Tightness
Abstract
Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but more efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces.
In this article, we present a new polynomial time procedure to decide tightness for triangulations of 3-manifolds - a problem which previously was thought to be hard. In addition, for the more difficult problem of deciding tightness of 4-dimensional combinatorial manifolds, we describe an algorithm that is fixed parameter tractable in the treewidth of the 1-skeletons of the vertex links. Finally, we show that simpler treewidth parameters are not viable: for all non-trivial inputs, we show that the treewidths of both the 1-skeleton and the dual graph must grow too quickly for a standard treewidth-based algorithm to remain tractable.
Cite as
Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, and Jonathan Spreer. Efficient Algorithms to Decide Tightness. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bagchi_et_al:LIPIcs.SoCG.2016.12,
author = {Bagchi, Bhaskar and Datta, Basudeb and Burton, Benjamin A. and Singh, Nitin and Spreer, Jonathan},
title = {{Efficient Algorithms to Decide Tightness}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {12:1--12:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.12},
URN = {urn:nbn:de:0030-drops-59040},
doi = {10.4230/LIPIcs.SoCG.2016.12},
annote = {Keywords: discrete geometry and topology, polynomial time algorithms, fixed parameter tractability, tight triangulations, simplicial complexes}
}
Document
Anchored Rectangle and Square Packings
Abstract
For points p_1,...,p_n in the unit square [0,1]^2, an anchored rectangle packing consists of interior-disjoint axis-aligned empty rectangles r_1,...,r_n in [0,1]^2 such that point p_i is a corner of the rectangle r_i (that is, r_i is anchored at p_i) for i=1,...,n. We show that for every set of n points in [0,1]^2, there is an anchored rectangle packing of area at least 7/12-O(1/n), and for every n, there are point sets for which the area of every anchored rectangle packing is at most 2/3. The maximum area of an anchored square packing is always at least 5/32 and sometimes at most 7/27.
The above constructive lower bounds immediately yield constant-factor approximations, of 7/12 -epsilon for rectangles and 5/32 for squares, for computing anchored packings of maximum area in O(n log n) time. We prove that a simple greedy strategy achieves a 9/47-approximation for anchored square packings, and 1/3 for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS and a PTAS for anchored rectangle and square packings in n^{O(1/epsilon)} and exp(poly(log (n/epsilon))) time, respectively.
Cite as
Kevin Balas, Adrian Dumitrescu, and Csaba Tóth. Anchored Rectangle and Square Packings. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{balas_et_al:LIPIcs.SoCG.2016.13,
author = {Balas, Kevin and Dumitrescu, Adrian and T\'{o}th, Csaba},
title = {{Anchored Rectangle and Square Packings}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {13:1--13:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.13},
URN = {urn:nbn:de:0030-drops-59054},
doi = {10.4230/LIPIcs.SoCG.2016.13},
annote = {Keywords: Rectangle packing, anchored rectangle, greedy algorithm, charging scheme, approximation algorithm.}
}
Document
On Variants of k-means Clustering
Abstract
Clustering problems often arise in fields like data mining and machine learning. Clustering usually refers to the task of partitioning a collection of objects into groups with similar elements, with respect to a similarity (or dissimilarity) measure. Among the clustering problems, k-means clustering in particular has received much attention from researchers. Despite the fact that k-means is a well studied problem, its status in the plane is still open. In particular, it is unknown whether it admits a PTAS in the plane. The best known approximation bound achievable in polynomial time is 9+epsilon.
In this paper, we consider the following variant of k-means. Given a set C of points in R^d and a real f > 0, find a finite set F of points in R^d that minimizes the quantity f*|F|+sum_{p in C} min_{q in F} {||p-q||}^2. For any fixed dimension d, we design a PTAS for this problem that is based on local search. We also give a "bi-criterion" local search algorithm for k-means which uses (1+epsilon)k centers and yields a solution whose cost is at most (1+epsilon) times the cost of an optimal k-means solution. The algorithm runs in polynomial time for any fixed dimension.
The contribution of this paper is two-fold. On the one hand, we are able to handle the square of distances in an elegant manner, obtaining a near-optimal approximation bound. This leads us towards a better understanding of the k-means problem. On the other hand, our analysis of local search might also be useful for other geometric problems. This is important considering that little is known about the local search method for geometric approximation.
Cite as
Sayan Bandyapadhyay and Kasturi Varadarajan. On Variants of k-means Clustering. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2016.14,
author = {Bandyapadhyay, Sayan and Varadarajan, Kasturi},
title = {{On Variants of k-means Clustering}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.14},
URN = {urn:nbn:de:0030-drops-59061},
doi = {10.4230/LIPIcs.SoCG.2016.14},
annote = {Keywords: k-means, Facility location, Local search, Geometric approximation}
}
Document
Incremental Voronoi diagrams
Abstract
We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram VD(S) (and several variants thereof) of a set S of n sites in the plane as sites are added to the set. To that effect, we define a general update operation for planar graphs that can be used to model the incremental construction of several variants of Voronoi diagrams as well as the incremental construction of an intersection of halfspaces in R^3. We show that the amortized number of edge insertions and removals needed to add a new site to the Voronoi diagram is O(n^(1/2)). A matching Omega(n^(1/2)) combinatorial lower bound is shown, even in the case where the graph representing the Voronoi diagram is a tree. This contrasts with the O(log(n)) upper bound of Aronov et al. [Aronov et al., in proc. of LATIN, 2006] for farthest-point Voronoi diagrams in the special case where points are inserted in clockwise order along their convex hull.
We then present a semi-dynamic data structure that maintains the Voronoi diagram of a set S of n sites in convex position. This data structure supports the insertion of a new site p (and hence the addition of its Voronoi cell) and finds the asymptotically minimal number K of edge insertions and removals needed to obtain the diagram of S U (p) from the diagram of S, in time O(K polylog n) worst case, which is O(n^(1/2) polylog n) amortized by the aforementioned combinatorial result.
The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained explicitly at all times and can be retrieved and traversed in the natural way; this contrasts with other known data structures supporting nearest neighbor queries. Our data structure supports general search operations on the current Voronoi diagram, which can, for example, be used to perform point location queries in the cells of the current Voronoi diagram in O(log n) time, or to determine whether two given sites are neighbors in the Delaunay triangulation.
Cite as
Sarah R. Allen, Luis Barba, John Iacono, and Stefan Langerman. Incremental Voronoi diagrams. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{allen_et_al:LIPIcs.SoCG.2016.15,
author = {Allen, Sarah R. and Barba, Luis and Iacono, John and Langerman, Stefan},
title = {{Incremental Voronoi diagrams}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {15:1--15:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.15},
URN = {urn:nbn:de:0030-drops-59079},
doi = {10.4230/LIPIcs.SoCG.2016.15},
annote = {Keywords: Voronoi diagrams, dynamic data structures, Delaunay triangulation}
}
Document
Dimension Reduction Techniques for l_p (1<p<2), with Applications
Abstract
For Euclidean space (l_2), there exists the powerful dimension reduction transform of Johnson and Lindenstrauss [Conf. in modern analysis and probability, AMS 1984], with a host of known applications. Here, we consider the problem of dimension reduction for all l_p spaces 1<p<2. Although strong lower bounds are known for dimension reduction in l_1, Ostrovsky and Rabani [JACM 2002] successfully circumvented these by presenting an l_1 embedding that maintains fidelity in only a bounded distance range, with applications to clustering and nearest neighbor search. However, their embedding techniques are specific to l_1 and do not naturally extend to other norms.
In this paper, we apply a range of advanced techniques and produce bounded range dimension reduction embeddings for all of 1<p<2, thereby demonstrating that the approach initiated by Ostrovsky and Rabani for l_1 can be extended to a much more general framework. We also obtain improved bounds in terms of the intrinsic dimensionality. As a result we achieve improved bounds for proximity problems including snowflake embeddings and clustering.
Cite as
Yair Bartal and Lee-Ad Gottlieb. Dimension Reduction Techniques for l_p (1<p<2), with Applications. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bartal_et_al:LIPIcs.SoCG.2016.16,
author = {Bartal, Yair and Gottlieb, Lee-Ad},
title = {{Dimension Reduction Techniques for l\underlinep (1\langlep\langle2), with Applications}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {16:1--16:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.16},
URN = {urn:nbn:de:0030-drops-59081},
doi = {10.4230/LIPIcs.SoCG.2016.16},
annote = {Keywords: Dimension reduction, embeddings}
}
Document
Testing Convexity of Figures Under the Uniform Distribution
Abstract
We consider the following basic geometric problem: Given epsilon in (0,1/2), a 2-dimensional figure that consists of a black object and a white background is epsilon-far from convex if it differs in at least an epsilon fraction of the area from every figure where the black object is convex. How many uniform and independent samples from a figure that is epsilon-far from convex are needed to detect a violation of convexity with probability at least 2/3? This question arises in the context of designing property testers for convexity. Specifically, a (1-sided error) tester for convexity gets samples from the figure, labeled by their color; it always accepts if the black object is convex; it rejects with probability at least 2/3 if the figure is epsilon-far from convex.
We show that Theta(epsilon^{-4/3}) uniform samples are necessary and sufficient for detecting a violation of convexity in an epsilon-far figure and, equivalently, for testing convexity of figures with 1-sided error. Our testing algorithm runs in time O(epsilon^{-4/3}) and thus beats the Omega(epsilon^{-3/2}) sample lower bound for learning convex figures under the uniform distribution from the work of Schmeltz (Data Structures and Efficient Algorithms,1992). It shows that, with uniform samples, we can check if a set is approximately convex much faster than we can find an approximate representation of a convex set.
Cite as
Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing Convexity of Figures Under the Uniform Distribution. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{berman_et_al:LIPIcs.SoCG.2016.17,
author = {Berman, Piotr and Murzabulatov, Meiram and Raskhodnikova, Sofya},
title = {{Testing Convexity of Figures Under the Uniform Distribution}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {17:1--17:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.17},
URN = {urn:nbn:de:0030-drops-59094},
doi = {10.4230/LIPIcs.SoCG.2016.17},
annote = {Keywords: Convex sets, 2D geometry, randomized algorithms, property testing}
}
Document
Separating a Voronoi Diagram via Local Search
Abstract
Given a set P of n points in R^d , we show how to insert a set Z of O(n^(1-1/d)) additional points, such that P can be broken into two sets P1 and P2 , of roughly equal size, such that in the Voronoi diagram V(P u Z), the cells of P1 do not touch the cells of P2; that is, Z separates P1 from P2 in the Voronoi diagram (and also in the dual Delaunay triangulation). In addition, given such a partition (P1,P2) of P , we present an approximation algorithm to compute a minimum size separator realizing this partition. We also present a simple local search algorithm that is a PTAS for approximating the optimal Voronoi partition.
Cite as
Vijay V. S. P. Bhattiprolu and Sariel Har-Peled. Separating a Voronoi Diagram via Local Search. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bhattiprolu_et_al:LIPIcs.SoCG.2016.18,
author = {Bhattiprolu, Vijay V. S. P. and Har-Peled, Sariel},
title = {{Separating a Voronoi Diagram via Local Search}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {18:1--18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.18},
URN = {urn:nbn:de:0030-drops-59107},
doi = {10.4230/LIPIcs.SoCG.2016.18},
annote = {Keywords: Separators, Local search, Approximation, Voronoi diagrams, Delaunay triangulation, Meshing, Geometric hitting set}
}
Document
On Visibility Representations of Non-Planar Graphs
Abstract
A rectangle visibility representation (RVR) of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NP-hard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is fixed and we are looking for an RVR that reflects this embedding. We show that in this case the problem can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs (i.e., embedded graphs having at most one crossing per edge). The linear time algorithm uses a precise list of forbidden configurations, which extends the set known for straight-line drawings of 1-plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1-plane graph has an RVR and either compute such a representation or report a negative witness. Finally, we discuss some extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge.
Cite as
Therese Biedl, Giuseppe Liotta, and Fabrizio Montecchiani. On Visibility Representations of Non-Planar Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{biedl_et_al:LIPIcs.SoCG.2016.19,
author = {Biedl, Therese and Liotta, Giuseppe and Montecchiani, Fabrizio},
title = {{On Visibility Representations of Non-Planar Graphs}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {19:1--19:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.19},
URN = {urn:nbn:de:0030-drops-59116},
doi = {10.4230/LIPIcs.SoCG.2016.19},
annote = {Keywords: Visibility Representations, 1-Planarity, Recognition Algorithm, Forbidden Configuration}
}
Document
Delaunay Triangulations on Orientable Surfaces of Low Genus
Abstract
Earlier work on Delaunay triangulation of point sets on the 2D flat torus, which is locally isometric to the Euclidean plane, was based on lifting the point set to a locally isometric 9-sheeted covering space of the torus. Under mild conditions the Delaunay triangulation of the lifted point set, consisting of 9 copies of the input set, projects to the Delaunay triangulation of the input set.
We improve and generalize this work. First we present a new construction based on an 8-sheeted covering space, which shows that eight copies suffice for the standard flat torus. Then we generalize this construction to the context of compact orientable surfaces of higher genus, which are locally isometric to the hyperbolic plane. We investigate more thoroughly the Bolza surface, homeomorphic to a sphere with two handles, both because it is the hyperbolic surface with lowest genus, and because triangulations on the Bolza surface have applications in various fields such as neuromathematics and cosmological models. While the general properties (existence results of appropriate covering spaces) show similarities with the results for the flat case, explicit constructions and their proofs are much more complex, even in the case of the apparently simple Bolza surface. One of the main reasons is the fact that two hyperbolic translations do not commute in general.
To the best of our knowledge, the results in this paper are the first ones of this kind. The interest of our contribution lies not only in the results, but most of all in the construction of covering spaces itself and the study of their properties.
Cite as
Mikhail Bogdanov, Monique Teillaud, and Gert Vegter. Delaunay Triangulations on Orientable Surfaces of Low Genus. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bogdanov_et_al:LIPIcs.SoCG.2016.20,
author = {Bogdanov, Mikhail and Teillaud, Monique and Vegter, Gert},
title = {{Delaunay Triangulations on Orientable Surfaces of Low Genus}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {20:1--20:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.20},
URN = {urn:nbn:de:0030-drops-59129},
doi = {10.4230/LIPIcs.SoCG.2016.20},
annote = {Keywords: covering spaces, hyperbolic surfaces, finitely presented groups, Fuchsian groups, systole}
}
Document
An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams
Abstract
Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O(k(n-k) log^2 n +n log^3 n) steps, where O(k(n-k)) is the number of faces in the worst case. Due to those axioms, this result applies to disjoint line segments in the L_p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, this kind of run time with a polylog factor to the number of faces was only achieved for point sites in the L_1 or Euclidean metric before.
Cite as
Cecilia Bohler, Rolf Klein, and Chih-Hung Liu. An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bohler_et_al:LIPIcs.SoCG.2016.21,
author = {Bohler, Cecilia and Klein, Rolf and Liu, Chih-Hung},
title = {{An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {21:1--21:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.21},
URN = {urn:nbn:de:0030-drops-59135},
doi = {10.4230/LIPIcs.SoCG.2016.21},
annote = {Keywords: Order-k Voronoi Diagrams, Abstract Voronoi Diagrams, Randomized Geometric Algorithms}
}
Document
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
Abstract
For an undirected n-vertex graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a minimum st-cut in G? We solve this problem in preprocessing time O(n log^3 n) for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space O(n) that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is 2^{O(g^2)}.
Cite as
Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{borradaile_et_al:LIPIcs.SoCG.2016.22,
author = {Borradaile, Glencora and Eppstein, David and Nayyeri, Amir and Wulff-Nilsen, Christian},
title = {{All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {22:1--22:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.22},
URN = {urn:nbn:de:0030-drops-59149},
doi = {10.4230/LIPIcs.SoCG.2016.22},
annote = {Keywords: minimum cuts, surface-embedded graphs, Gomory-Hu tree}
}
Document
Minimum Cycle and Homology Bases of Surface Embedded Graphs
Abstract
We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1-dimensional (Z_2)-homology classes) of an undirected graph embedded on an orientable surface of genus g. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis.
For the minimum cycle basis problem, we give a deterministic O(n^omega + 2^2g n^2)-time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA'09] and a deterministic O(n^3) time algorithm [Mehlhorn and Michail, TALG'09]. For the minimum homology basis problem, we give an O(g^3 n log n)-time algorithm, improving on existing algorithms for many values of g and n.
Cite as
Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri. Minimum Cycle and Homology Bases of Surface Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{borradaile_et_al:LIPIcs.SoCG.2016.23,
author = {Borradaile, Glencora and Chambers, Erin Wolf and Fox, Kyle and Nayyeri, Amir},
title = {{Minimum Cycle and Homology Bases of Surface Embedded Graphs}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {23:1--23:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.23},
URN = {urn:nbn:de:0030-drops-59152},
doi = {10.4230/LIPIcs.SoCG.2016.23},
annote = {Keywords: Cycle basis, Homology basis, Topological graph theory}
}
Document
Finding Non-Orientable Surfaces in 3-Manifolds
Abstract
We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds.
We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.
Cite as
Benjamin A. Burton, Arnaud de Mesmay, and Uli Wagner. Finding Non-Orientable Surfaces in 3-Manifolds. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{burton_et_al:LIPIcs.SoCG.2016.24,
author = {Burton, Benjamin A. and de Mesmay, Arnaud and Wagner, Uli},
title = {{Finding Non-Orientable Surfaces in 3-Manifolds}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {24:1--24:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.24},
URN = {urn:nbn:de:0030-drops-59168},
doi = {10.4230/LIPIcs.SoCG.2016.24},
annote = {Keywords: 3-manifold, low-dimensional topology, embedding, non-orientability, normal surfaces}
}
Document
Structure and Stability of the 1-Dimensional Mapper
Abstract
Given a continuous function f:X->R and a cover I of its image by intervals, the Mapper is the nerve of a refinement of the pullback cover f^{-1}(I). Despite its success in applications, little is known about the structure and stability of this construction from a theoretical point of view. As a pixelized version of the Reeb graph of f, it is expected to capture a subset of its features (branches, holes), depending on how the interval cover is positioned with respect to the critical values of the function. Its stability should also depend on this positioning. We propose a theoretical framework relating the structure of the Mapper to that of the Reeb graph, making it possible to predict which features will be present and which will be absent in the Mapper given the function and the cover, and for each feature, to quantify its degree of (in-)stability. Using this framework, we can derive guarantees on the structure of the Mapper, on its stability, and on its convergence to the Reeb graph as the granularity of the cover I goes to zero.
Cite as
Mathieu Carrière and Steve Oudot. Structure and Stability of the 1-Dimensional Mapper. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{carriere_et_al:LIPIcs.SoCG.2016.25,
author = {Carri\`{e}re, Mathieu and Oudot, Steve},
title = {{Structure and Stability of the 1-Dimensional Mapper}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {25:1--25:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.25},
URN = {urn:nbn:de:0030-drops-59175},
doi = {10.4230/LIPIcs.SoCG.2016.25},
annote = {Keywords: Mapper, Reeb Graph, Extended Persistence, Topological Data Analysis}
}
Document
Max-Sum Diversity Via Convex Programming
Abstract
Diversity maximization is an important concept in information retrieval, computational geometry and operations research. Usually, it is a variant of the following problem: Given a ground set, constraints, and a function f that measures diversity of a subset, the task is to select a feasible subset S such that f(S) is maximized. The sum-dispersion function f(S) which is the sum of the pairwise distances in S, is in this context a prominent diversification measure. The corresponding diversity maximization is the "max-sum" or "sum-sum" diversification. Many recent results deal with the design of constant-factor approximation algorithms of diversification problems involving sum-dispersion function under a matroid constraint.
In this paper, we present a PTAS for the max-sum diversity problem under a matroid constraint for distances d(.,.) of negative type. Distances of negative type are, for example, metric distances stemming from the l_2 and l_1 norms, as well as the cosine or spherical, or Jaccard distance which are popular similarity metrics in web and image search.
Our algorithm is based on techniques developed in geometric algorithms like metric embeddings and convex optimization. We show that one can compute a fractional solution of the usually non-convex relaxation of the problem which yields an upper bound on the optimum integer solution. Starting from this fractional solution, we employ a deterministic rounding approach which only incurs a small loss in terms of objective, thus leading to a PTAS. This technique can be applied to other previously studied variants of the max-sum dispersion function, including combinations of diversity with linear-score maximization, improving over the previous constant-factor approximation algorithms.
Cite as
Alfonso Cevallos, Friedrich Eisenbrand, and Rico Zenklusen. Max-Sum Diversity Via Convex Programming. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{cevallos_et_al:LIPIcs.SoCG.2016.26,
author = {Cevallos, Alfonso and Eisenbrand, Friedrich and Zenklusen, Rico},
title = {{Max-Sum Diversity Via Convex Programming}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {26:1--26:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.26},
URN = {urn:nbn:de:0030-drops-59186},
doi = {10.4230/LIPIcs.SoCG.2016.26},
annote = {Keywords: Geometric Dispersion, Embeddings, Approximation Algorithms, Convex Programming, Matroids}
}
Document
Dynamic Streaming Algorithms for Epsilon-Kernels
Abstract
Introduced by Agarwal, Har-Peled, and Varadarajan [J. ACM, 2004], an epsilon-kernel of a point set is a coreset that can be used to approximate the width, minimum enclosing cylinder, minimum bounding box, and solve various related geometric optimization problems. Such coresets form one of the most important tools in the design of linear-time approximation algorithms in computational geometry, as well as efficient insertion-only streaming algorithms and dynamic (non-streaming) data structures. In this paper, we continue the theme and explore dynamic streaming algorithms (in the so-called turnstile model).
Andoni and Nguyen [SODA 2012] described a dynamic streaming algorithm for maintaining a (1+epsilon)-approximation of the width using O(polylog U) space and update time for a point set in [U]^d for any constant dimension d and any constant epsilon>0. Their sketch, based on a "polynomial method", does not explicitly maintain an epsilon-kernel. We extend their method to maintain an epsilon-kernel, and at the same time reduce some of logarithmic factors. As an application, we obtain the first randomized dynamic streaming algorithm for the width problem (and related geometric optimization problems) that supports k outliers, using poly(k, log U) space and time.
Cite as
Timothy M. Chan. Dynamic Streaming Algorithms for Epsilon-Kernels. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 27:1-27:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{chan:LIPIcs.SoCG.2016.27,
author = {Chan, Timothy M.},
title = {{Dynamic Streaming Algorithms for Epsilon-Kernels}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {27:1--27:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.27},
URN = {urn:nbn:de:0030-drops-59198},
doi = {10.4230/LIPIcs.SoCG.2016.27},
annote = {Keywords: coresets, streaming algorithms, dynamic algorithms, polynomial method, randomization, outliers}
}
Document
Two Approaches to Building Time-Windowed Geometric Data Structures
Abstract
Given a set of geometric objects each associated with a time value, we wish to determine whether a given property is true for a subset of those objects whose time values fall within a query time window. We call such problems time-windowed decision problems, and they have been the subject of much recent attention, for instance studied by Bokal, Cabello, and Eppstein [SoCG 2015]. In this paper, we present new approaches to this class of problems that are conceptually simpler than Bokal et al.'s, and also lead to faster algorithms. For instance, we present algorithms for preprocessing for the time-windowed 2D diameter decision problem in O(n log n) time and the time-windowed 2D convex hull area decision problem in O(n alpha(n) log n) time (where alpha is the inverse Ackermann function), improving Bokal et al.'s O(n log^2 n) and O(n log n loglog n) solutions respectively.
Our first approach is to reduce time-windowed decision problems to a generalized range successor problem, which we solve using a novel way to search range trees. Our other approach is to use dynamic data structures directly, taking advantage of a new observation that the total number of combinatorial changes to a planar convex hull is near linear for any FIFO update sequence, in which deletions occur in the same order as insertions. We also apply these approaches to obtain the first O(n polylog n) algorithms for the time-windowed 3D diameter decision and 2D orthogonal segment intersection detection problems.
Cite as
Timothy M. Chan and Simon Pratt. Two Approaches to Building Time-Windowed Geometric Data Structures. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{chan_et_al:LIPIcs.SoCG.2016.28,
author = {Chan, Timothy M. and Pratt, Simon},
title = {{Two Approaches to Building Time-Windowed Geometric Data Structures}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {28:1--28:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.28},
URN = {urn:nbn:de:0030-drops-59201},
doi = {10.4230/LIPIcs.SoCG.2016.28},
annote = {Keywords: time window, geometric data structures, range searching, dynamic convex hull}
}
Document
Untangling Planar Curves
Abstract
Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a planar closed curve with n self-crossings requires Theta(n^{3/2}) homotopy moves in the worst case. Our algorithm improves the best previous upper bound O(n^2), which is already implicit in the classical work of Steinitz; the matching lower bound follows from the construction of closed curves with large defect, a topological invariant of generic closed curves introduced by Aicardi and Arnold. This lower bound also implies that Omega(n^{3/2}) degree-1 reductions, series-parallel reductions, and Delta-Y transformations are required to reduce any planar graph with treewidth Omega(sqrt{n}) to a single edge, matching known upper bounds for rectangular and cylindrical grid graphs. Finally, we prove that Omega(n^2) homotopy moves are required in the worst case to transform one non-contractible closed curve on the torus to another; this lower bound is tight if the curve is homotopic to a simple closed curve.
Cite as
Hsien-Chih Chang and Jeff Erickson. Untangling Planar Curves. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{chang_et_al:LIPIcs.SoCG.2016.29,
author = {Chang, Hsien-Chih and Erickson, Jeff},
title = {{Untangling Planar Curves}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {29:1--29:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.29},
URN = {urn:nbn:de:0030-drops-59218},
doi = {10.4230/LIPIcs.SoCG.2016.29},
annote = {Keywords: computational topology, homotopy, planar graphs, Delta-Y transformations, defect, Reidemeister moves, tangles}
}
Document
Inserting Multiple Edges into a Planar Graph
Abstract
Let G be a connected planar (but not yet embedded) graph and F a set of additional edges not in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. An optimal solution to this problem is known to approximate the crossing number of the graph G+F.
Finding an exact solution to MEI is NP-hard for general F, but linear time solvable for the special case of |F|=1 [Gutwenger et al, SODA 2001/Algorithmica] and polynomial time solvable when all of F are incident to a new vertex [Chimani et al, SODA 2009]. The complexity for general F but with constant k=|F| was open, but algorithms both with relative and absolute approximation guarantees have been presented [Chuzhoy et al, SODA 2011], [Chimani-Hlineny, ICALP 2011]. We show that the problem is fixed parameter tractable (FPT) in k for biconnected G, or if the cut vertices of G have bounded degrees. We give the first exact algorithm for this problem; it requires only O(|V(G)|) time for any constant k.
Cite as
Markus Chimani and Petr Hlinený. Inserting Multiple Edges into a Planar Graph. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{chimani_et_al:LIPIcs.SoCG.2016.30,
author = {Chimani, Markus and Hlinen\'{y}, Petr},
title = {{Inserting Multiple Edges into a Planar Graph}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {30:1--30:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.30},
URN = {urn:nbn:de:0030-drops-59223},
doi = {10.4230/LIPIcs.SoCG.2016.30},
annote = {Keywords: crossing number, edge insertion, parameterized complexity, path homotopy, funnel algorithm}
}
Document
Polynomial-Sized Topological Approximations Using the Permutahedron
Abstract
Classical methods to model topological properties of point clouds, such as the Vietoris-Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for n points in R^d, we obtain a O(d)-approximation with at most n2^{O(d log k)} simplices of dimension k or lower. In conjunction with dimension reduction techniques, our approach yields a O(polylog (n))-approximation of size n^{O(1)} for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry.
Building on the same geometric concept, we also present a lower bound result on the size of an approximate filtration: we construct a point set for which every (1+epsilon)-approximation of the Cech filtration has to contain n^{Omega(log log n)} features, provided that epsilon < 1/(log^{1+c}n) for c in (0,1).
Cite as
Aruni Choudhary, Michael Kerber, and Sharath Raghvendra. Polynomial-Sized Topological Approximations Using the Permutahedron. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{choudhary_et_al:LIPIcs.SoCG.2016.31,
author = {Choudhary, Aruni and Kerber, Michael and Raghvendra, Sharath},
title = {{Polynomial-Sized Topological Approximations Using the Permutahedron}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {31:1--31:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.31},
URN = {urn:nbn:de:0030-drops-59236},
doi = {10.4230/LIPIcs.SoCG.2016.31},
annote = {Keywords: Persistent Homology, Topological Data Analysis, Simplicial Approximation, Permutahedron, Approximation Algorithms}
}
Document
Faster Algorithms for Computing Plurality Points
Abstract
Let V be a set of n points in R^d, which we call voters, where d is a fixed constant. A point p in R^d is preferred over another point p' in R^d by a voter v in V if dist(v,p) < dist(v,p'). A point p is called a plurality point if it is preferred by at least as many voters as any other point p'.
We present an algorithm that decides in O(n log n) time whether V admits a plurality point in the L_2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute the smallest subset W of V such that V - W admits a plurality point, and to compute a so-called minimum-radius plurality ball.
Finally, we consider the problem in the personalized L_1 norm, where each point v in V has a preference vector <w_1(v), ...,w_d(v)> and the distance from v to any point p in R^d is given by sum_{i=1}^d w_i(v) cdot |x_i(v)-x_i(p)|. For this case we can compute in O(n^(d-1)) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n).
Cite as
Mark de Berg, Joachim Gudmundsson, and Mehran Mehr. Faster Algorithms for Computing Plurality Points. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{deberg_et_al:LIPIcs.SoCG.2016.32,
author = {de Berg, Mark and Gudmundsson, Joachim and Mehr, Mehran},
title = {{Faster Algorithms for Computing Plurality Points}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {32:1--32:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.32},
URN = {urn:nbn:de:0030-drops-59248},
doi = {10.4230/LIPIcs.SoCG.2016.32},
annote = {Keywords: computational geometry, computational social choice, voting theory, plurality points, Condorcet points}
}
Document
Qualitative Symbolic Perturbation
Abstract
In a classical Symbolic Perturbation scheme, degeneracies are handled by substituting some polynomials in epsilon for the inputs of a predicate. Instead of a single perturbation, we propose to use a sequence of (simpler) perturbations. Moreover, we look at their effects geometrically instead of algebraically; this allows us to tackle cases that were not tractable with the classical algebraic approach.
Cite as
Olivier Devillers, Menelaos Karavelas, and Monique Teillaud. Qualitative Symbolic Perturbation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{devillers_et_al:LIPIcs.SoCG.2016.33,
author = {Devillers, Olivier and Karavelas, Menelaos and Teillaud, Monique},
title = {{Qualitative Symbolic Perturbation}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {33:1--33:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.33},
URN = {urn:nbn:de:0030-drops-59259},
doi = {10.4230/LIPIcs.SoCG.2016.33},
annote = {Keywords: Robustness issues, Symbolic perturbations, Apollonius diagram}
}
Document
Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance
Abstract
Truth Discovery is an important problem arising in data analytics related fields such as data mining, database, and big data. It concerns about finding the most trustworthy information from a dataset acquired from a number of unreliable sources. Due to its importance, the problem has been extensively studied in recent years and a number techniques have already been proposed. However, all of them are of heuristic nature and do not have any quality guarantee. In this paper, we formulate the problem as a high dimensional geometric optimization problem, called Entropy based Geometric Variance. Relying on a number of novel geometric techniques (such as Log-Partition and Modified Simplex Lemma), we further discover new insights to this problem. We show, for the first time, that the truth discovery problem can be solved with guaranteed quality of solution. Particularly, we show that it is possible to achieve a (1+eps)-approximation within nearly linear time under some reasonable assumptions. We expect that our algorithm will be useful for other data related applications.
Cite as
Hu Ding, Jing Gao, and Jinhui Xu. Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{ding_et_al:LIPIcs.SoCG.2016.34,
author = {Ding, Hu and Gao, Jing and Xu, Jinhui},
title = {{Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {34:1--34:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.34},
URN = {urn:nbn:de:0030-drops-59264},
doi = {10.4230/LIPIcs.SoCG.2016.34},
annote = {Keywords: geometric optimization, data mining, high dimension, entropy}
}
Document
On Expansion and Topological Overlap
Abstract
We give a detailed and easily accessible proof of Gromov's Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map X -> R^d there exists a point p in R^d whose preimage intersects a positive fraction mu > 0 of the d-cells of X. More generally, the conclusion holds if R^d is replaced by any d-dimensional piecewise-linear (PL) manifold M, with a constant \mu that depends only on d and on the expansion properties of X, but not on M.
Cite as
Dominic Dotterrer, Tali Kaufman, and Uli Wagner. On Expansion and Topological Overlap. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 35:1-35:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{dotterrer_et_al:LIPIcs.SoCG.2016.35,
author = {Dotterrer, Dominic and Kaufman, Tali and Wagner, Uli},
title = {{On Expansion and Topological Overlap}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {35:1--35:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.35},
URN = {urn:nbn:de:0030-drops-59270},
doi = {10.4230/LIPIcs.SoCG.2016.35},
annote = {Keywords: Combinatorial Topology, Selection Lemmas, Higher-Dimensional Expanders}
}
Document
On the Number of Maximum Empty Boxes Amidst n Points
Abstract
We revisit the following problem (along with its higher dimensional variant): Given a set S of n points inside an axis-parallel rectangle U in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in U but contains no points of S.
1. We prove that the number of maximum-area empty rectangles amidst n points in the plane is O(n log n 2^alpha(n)), where alpha(n) is the extremely slowly growing inverse of Ackermann's function. The previous best bound, O(n^2), is due to Naamad, Lee, and Hsu (1984).
2. For any d at least 3, we prove that the number of maximum-volume empty boxes amidst n points in R^d is always O(n^d) and sometimes Omega(n^floor(d/2)).
This is the first superlinear lower bound derived for this problem.
3. We discuss some algorithmic aspects regarding the search for a maximum empty box in R^3. In particular, we present an algorithm that finds a (1-epsilon)-approximation of the maximum empty box amidst n points in O(epsilon^{-2} n^{5/3} log^2{n}) time.
Cite as
Adrian Dumitrescu and Minghui Jiang. On the Number of Maximum Empty Boxes Amidst n Points. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{dumitrescu_et_al:LIPIcs.SoCG.2016.36,
author = {Dumitrescu, Adrian and Jiang, Minghui},
title = {{On the Number of Maximum Empty Boxes Amidst n Points}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {36:1--36:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.36},
URN = {urn:nbn:de:0030-drops-59281},
doi = {10.4230/LIPIcs.SoCG.2016.36},
annote = {Keywords: Maximum empty box, Davenport-Schinzel sequence, approximation algorithm, data mining.}
}
Document
Strongly Monotone Drawings of Planar Graphs
Abstract
A straight-line drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices.
We present algorithms to compute crossing-free strongly monotone drawings for some classes of planar graphs; namely, 3-connected planar graphs, outerplanar graphs, and 2-trees. The drawings of 3-connected planar graphs are based on primal-dual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.
Cite as
Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze, and Manfred Scheucher. Strongly Monotone Drawings of Planar Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{felsner_et_al:LIPIcs.SoCG.2016.37,
author = {Felsner, Stefan and Igamberdiev, Alexander and Kindermann, Philipp and Klemz, Boris and Mchedlidze, Tamara and Scheucher, Manfred},
title = {{Strongly Monotone Drawings of Planar Graphs}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {37:1--37:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.37},
URN = {urn:nbn:de:0030-drops-59292},
doi = {10.4230/LIPIcs.SoCG.2016.37},
annote = {Keywords: graph drawing, planar graphs, strongly monotone, strictly convex, primal-dual circle packing}
}
Document
Hyperplane Separability and Convexity of Probabilistic Point Sets
Abstract
We describe an O(n^d) time algorithm for computing the exact probability that two d-dimensional probabilistic point sets are linearly separable, for any fixed d >= 2. A probabilistic point in d-space is the usual point, but with an associated (independent) probability of existence. We also show that the d-dimensional separability problem is equivalent to a (d+1)-dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of n probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership by a factor of n [Agarwal et al., ESA, 2014]. In addition, our algorithms can handle "input degeneracies" in which more than k+1 points may lie on a k-dimensional subspace, thus resolving an open problem in [Agarwal et al., ESA, 2014]. Finally, we prove lower bounds for the separability problem via a reduction from the k-SUM problem, which shows in particular that our O(n^2) algorithms for 2-dimensional separability and 3-dimensional convex hull membership are nearly optimal.
Cite as
Martin Fink, John Hershberger, Nirman Kumar, and Subhash Suri. Hyperplane Separability and Convexity of Probabilistic Point Sets. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{fink_et_al:LIPIcs.SoCG.2016.38,
author = {Fink, Martin and Hershberger, John and Kumar, Nirman and Suri, Subhash},
title = {{Hyperplane Separability and Convexity of Probabilistic Point Sets}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {38:1--38:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.38},
URN = {urn:nbn:de:0030-drops-59305},
doi = {10.4230/LIPIcs.SoCG.2016.38},
annote = {Keywords: probabilistic separability, uncertain data, 3-SUM hardness, topological sweep, hyperplane separation, multi-dimensional data}
}
Document
Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
Abstract
A rectilinear Steiner tree for a set T of points in the plane is a tree which connects T using horizontal and vertical lines. In the Rectilinear Steiner Tree problem, input is a set T of n points in the Euclidean plane (R^2) and the goal is to find an rectilinear Steiner tree for T of smallest possible total length. A rectilinear Steiner arborecence for a set T of points and root r in T is a rectilinear Steiner tree S for T such that the path in S from r to any point t in T is a shortest path. In the Rectilinear Steiner Arborescense problem the input is a set T of n points in R^2, and a root r in T, the task is to find an rectilinear Steiner arborescence for T, rooted at r of smallest possible total length. In this paper, we give the first subexponential time algorithms for both problems. Our algorithms are deterministic and run in 2^{O(sqrt{n}log n)} time.
Cite as
Fedor Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{fomin_et_al:LIPIcs.SoCG.2016.39,
author = {Fomin, Fedor and Kolay, Sudeshna and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket},
title = {{Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {39:1--39:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.39},
URN = {urn:nbn:de:0030-drops-59310},
doi = {10.4230/LIPIcs.SoCG.2016.39},
annote = {Keywords: Rectilinear graphs, Steiner arborescence, parameterized algorithms}
}
Document
Random Sampling with Removal
Abstract
Random sampling is a classical tool in constrained optimization. Under favorable conditions, the optimal solution subject to a small subset of randomly chosen constraints violates only a small subset of the remaining constraints. Here we study the following variant that we call random sampling with removal: suppose that after sampling the subset, we remove a fixed number of constraints from the sample, according to an arbitrary rule. Is it still true that the optimal solution of the reduced sample violates only a small subset of the constraints?
The question naturally comes up in situations where the solution subject to the sampled constraints is used as an approximate solution to the original problem. In this case, it makes sense to improve cost and volatility of the sample solution by removing some of the constraints that appear most restricting. At the same time, the approximation quality (measured in terms of violated constraints) should remain high.
We study random sampling with removal in a generalized, completely abstract setting where we assign to each subset R of the constraints an arbitrary set V(R) of constraints disjoint from R; in applications, V(R) corresponds to the constraints violated by the optimal solution subject to only the constraints in R. Furthermore, our results are parametrized by the dimension d, i.e., we assume that every set R has a subset B of size at most d with the same set of violated constraints. This is the first time this generalized setting is studied.
In this setting, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of k elements. For a large range of values of k, the new upper bounds improve the previously best bounds for LP-type problems, which moreover had only been known in special cases. We show that this bound on special LP-type problems, can be derived in the much more general setting of violator spaces, and with very elementary proofs.
Cite as
Bernd Gärtner, Johannes Lengler, and May Szedlák. Random Sampling with Removal. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{gartner_et_al:LIPIcs.SoCG.2016.40,
author = {G\"{a}rtner, Bernd and Lengler, Johannes and Szedl\'{a}k, May},
title = {{Random Sampling with Removal}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {40:1--40:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.40},
URN = {urn:nbn:de:0030-drops-59328},
doi = {10.4230/LIPIcs.SoCG.2016.40},
annote = {Keywords: LP-type problem, violator space, random sampling, sampling with removal}
}
Document
The Planar Tree Packing Theorem
Abstract
Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees T1 and T2 on n vertices and have to find a planar graph on n vertices that is the edge-disjoint union of T1 and T2. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of Garcia et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given nonstar trees.
Cite as
Markus Geyer, Michael Hoffmann, Michael Kaufmann, Vincent Kusters, and Csaba Tóth. The Planar Tree Packing Theorem. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{geyer_et_al:LIPIcs.SoCG.2016.41,
author = {Geyer, Markus and Hoffmann, Michael and Kaufmann, Michael and Kusters, Vincent and T\'{o}th, Csaba},
title = {{The Planar Tree Packing Theorem}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {41:1--41:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.41},
URN = {urn:nbn:de:0030-drops-59337},
doi = {10.4230/LIPIcs.SoCG.2016.41},
annote = {Keywords: graph drawing, simultaneous embedding, planar graph, graph packin}
}
Document
Crossing Number is Hard for Kernelization
Abstract
The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixed-parameter tractable for the parameter k [Grohe, STOC 2001]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time reduced to an equivalent instance of size polynomial in k (and independent of |G|). We answer this question in the negative. Along the proof we show that the tile crossing number problem of twisted planar tiles is NP-hard, which has been an open problem for some time, too, and then employ the complexity technique of cross-composition. Our result holds already for the special case of graphs obtained from planar graphs by adding one edge.
Cite as
Petr Hlinený and Marek Dernár. Crossing Number is Hard for Kernelization. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 42:1-42:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{hlineny_et_al:LIPIcs.SoCG.2016.42,
author = {Hlinen\'{y}, Petr and Dern\'{a}r, Marek},
title = {{Crossing Number is Hard for Kernelization}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {42:1--42:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.42},
URN = {urn:nbn:de:0030-drops-59347},
doi = {10.4230/LIPIcs.SoCG.2016.42},
annote = {Keywords: crossing number; tile crossing number; parameterized complexity; polynomial kernel; cross-composition}
}
Document
Shortest Path Embeddings of Graphs on Surfaces
Abstract
The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest path between its two endpoints and we call an embedding with this property a shortest path embedding. The main question addressed in this paper is whether given a closed surface S, there exists a Riemannian metric for which every topologically embeddable graph admits a shortest path embedding. This question is also motivated by various problems regarding crossing numbers on surfaces.
We observe that the round metrics on the sphere and the projective plane have this property. We provide flat metrics on the torus and the Klein bottle which also have this property.
Then we show that for the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. We show, moreover, that for large g, there exist graphs G embeddable into the orientable surface of genus g, such that with large probability a random hyperbolic metric does not admit a shortest path embedding of G, where the probability measure is proportional to the Weil-Petersson volume on moduli space.
Finally, we construct a hyperbolic metric on every orientable surface S of genus g, such that every graph embeddable into S can be embedded so that every edge is a concatenation of at most O(g) shortest paths.
Cite as
Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, and Martin Tancer. Shortest Path Embeddings of Graphs on Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{hubard_et_al:LIPIcs.SoCG.2016.43,
author = {Hubard, Alfredo and Kalu\v{z}a, Vojtech and de Mesmay, Arnaud and Tancer, Martin},
title = {{Shortest Path Embeddings of Graphs on Surfaces}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {43:1--43:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.43},
URN = {urn:nbn:de:0030-drops-59356},
doi = {10.4230/LIPIcs.SoCG.2016.43},
annote = {Keywords: Graph embedding, surface, shortest path, crossing number, hyperbolic geometry}
}
Document
Simultaneous Nearest Neighbor Search
Abstract
Motivated by applications in computer vision and databases, we introduce and study the Simultaneous Nearest Neighbor Search (SNN) problem. Given a set of data points, the goal of SNN is to design a data structure that, given a collection of queries, finds a collection of close points that are compatible with each other. Formally, we are given k query points Q=q_1,...,q_k, and a compatibility graph G with vertices in Q, and the goal is to return data points p_1,...,p_k that minimize (i) the weighted sum of the distances from q_i to p_i and (ii) the weighted sum, over all edges (i,j) in the compatibility graph G, of the distances between p_i and p_j. The problem has several applications in computer vision and databases, where one wants to return a set of *consistent* answers to multiple related queries. Furthermore, it generalizes several well-studied computational problems, including Nearest Neighbor Search, Aggregate Nearest Neighbor Search and the 0-extension problem.
In this paper we propose and analyze the following general two-step method for designing efficient data structures for SNN. In the first step, for each query point q_i we find its (approximate) nearest neighbor point p'_i; this can be done efficiently using existing approximate nearest neighbor structures. In the second step, we solve an off-line optimization problem over sets q_1,...,q_k and p'_1,...,p'_k; this can be done efficiently given that k is much smaller than n. Even though p'_1,...,p'_k might not constitute the optimal answers to queries q_1,...,q_k, we show that, for the unweighted case, the resulting algorithm satisfies a O(log k/log log k)-approximation guarantee. Furthermore, we show that the approximation factor can be in fact reduced to a constant for compatibility graphs frequently occurring in practice, e.g., 2D grids, 3D grids or planar graphs.
Finally, we validate our theoretical results by preliminary experiments. In particular, we show that the empirical approximation factor provided by the above approach is very close to 1.
Cite as
Piotr Indyk, Robert Kleinberg, Sepideh Mahabadi, and Yang Yuan. Simultaneous Nearest Neighbor Search. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{indyk_et_al:LIPIcs.SoCG.2016.44,
author = {Indyk, Piotr and Kleinberg, Robert and Mahabadi, Sepideh and Yuan, Yang},
title = {{Simultaneous Nearest Neighbor Search}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {44:1--44:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.44},
URN = {urn:nbn:de:0030-drops-59360},
doi = {10.4230/LIPIcs.SoCG.2016.44},
annote = {Keywords: Approximate Nearest Neighbor, Metric Labeling, 0-extension, Simultaneous Nearest Neighbor, Group Nearest Neighbor}
}
Document
Degree Four Plane Spanners: Simpler and Better
Abstract
Let P be a set of n points embedded in the plane, and let C be the complete Euclidean graph whose point-set is P. Each edge in C between two points p, q is realized as the line segment [pq], and is assigned a weight equal to the Euclidean distance |pq|. In this paper, we show how to construct in O(nlg{n}) time a plane spanner of C of maximum degree at most 4 and of stretch factor at most 20. This improves a long sequence of results on the construction of bounded degree plane spanners of C. Our result matches the smallest known upper bound of 4 by Bonichon et al. on the maximum degree while significantly improving their stretch factor upper bound from 156.82 to 20. The construction of our spanner is based on Delaunay triangulations defined with respect to the equilateral-triangle distance, and uses a different approach than that used by Bonichon et al. Our approach leads to a simple and intuitive construction of a well-structured spanner, and reveals useful structural properties of the Delaunay triangulations defined with respect to the equilateral-triangle distance.
Cite as
Iyad Kanj, Ljubomir Perkovic, and Duru Türkoglu. Degree Four Plane Spanners: Simpler and Better. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{kanj_et_al:LIPIcs.SoCG.2016.45,
author = {Kanj, Iyad and Perkovic, Ljubomir and T\"{u}rkoglu, Duru},
title = {{Degree Four Plane Spanners: Simpler and Better}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {45:1--45:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.45},
URN = {urn:nbn:de:0030-drops-59376},
doi = {10.4230/LIPIcs.SoCG.2016.45},
annote = {Keywords: Nonnumerical Algorithms and Problems,Computational Geometry and Object Modeling}
}
Document
A Lower Bound on Opaque Sets
Abstract
It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.
Cite as
Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, and János Pach. A Lower Bound on Opaque Sets. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 46:1-46:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{kawamura_et_al:LIPIcs.SoCG.2016.46,
author = {Kawamura, Akitoshi and Moriyama, Sonoko and Otachi, Yota and Pach, J\'{a}nos},
title = {{A Lower Bound on Opaque Sets}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {46:1--46:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.46},
URN = {urn:nbn:de:0030-drops-59386},
doi = {10.4230/LIPIcs.SoCG.2016.46},
annote = {Keywords: barriers; Cauchy-Crofton formula; lower bound; opaque sets}
}
Document
Fixed Points of the Restricted Delaunay Triangulation Operator
Abstract
The restricted Delaunay triangulation can be conceived as an operator that takes as input a k-manifold (typically smooth) embedded in R^d and a set of points sampled with sufficient density on that manifold, and produces as output a k-dimensional triangulation of the manifold, the input points serving as its vertices. What happens if we feed that triangulation back into the operator, replacing the original manifold, while retaining the same set of input points? If k = 2 and the sample points are sufficiently dense, we obtain another triangulation of the manifold. Iterating this process, we soon reach an iteration for which the input and output triangulations are the same. We call this triangulation a fixed point of the restricted Delaunay triangulation operator.
With this observation, and a new test for distinguishing "critical points" near the manifold from those near its medial axis, we develop a provably good surface reconstruction algorithm for R^3 with unusually modest sampling requirements. We develop a similar algorithm for constructing a simplicial complex that models a 2-manifold embedded in a high-dimensional space R^d, also with modest sampling requirements (especially compared to algorithms that depend on sliver exudation). The latter algorithm builds a non-manifold representation similar to the flow complex, but made solely of Delaunay simplices. The algorithm avoids the curse of dimensionality: its running time is polynomial, not exponential, in d.
Cite as
Marc Khoury and Jonathan Richard Shewchuk. Fixed Points of the Restricted Delaunay Triangulation Operator. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{khoury_et_al:LIPIcs.SoCG.2016.47,
author = {Khoury, Marc and Shewchuk, Jonathan Richard},
title = {{Fixed Points of the Restricted Delaunay Triangulation Operator}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {47:1--47:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.47},
URN = {urn:nbn:de:0030-drops-59396},
doi = {10.4230/LIPIcs.SoCG.2016.47},
annote = {Keywords: restricted Delaunay triangulation, fixed point, manifold reconstruction, surface reconstruction, computational geometry}
}
Document
Congruence Testing of Point Sets in 4-Space
Abstract
We give a deterministic O(n log n)-time algorithm to decide if two n-point sets in 4-dimensional Euclidean space are the same up to rotations and translations. It has been conjectured that O(n log n) algorithms should exist for any fixed dimension. The best algorithms in d-space so far are a deterministic algorithm by Brass and Knauer [Int. J. Comput. Geom. Appl., 2000] and a randomized Monte Carlo algorithm by Akutsu [Comp. Geom., 1998]. They take time O(n^2 log n) and O(n^(3/2) log n) respectively in 4-space. Our algorithm exploits many geometric structures and properties of 4-dimensional space.
Cite as
Heuna Kim and Günter Rote. Congruence Testing of Point Sets in 4-Space. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{kim_et_al:LIPIcs.SoCG.2016.48,
author = {Kim, Heuna and Rote, G\"{u}nter},
title = {{Congruence Testing of Point Sets in 4-Space}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {48:1--48:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.48},
URN = {urn:nbn:de:0030-drops-59409},
doi = {10.4230/LIPIcs.SoCG.2016.48},
annote = {Keywords: Congruence Testing Algorithm, Symmetry, Computational Geometry}
}
Document
On the Complexity of Minimum-Link Path Problems
Abstract
We revisit the minimum-link path problem: Given a polyhedral domain and two points in it, connect the points by a polygonal path with minimum number of edges. We consider settings where the min-link path's vertices or edges can be restricted to lie on the boundary of the domain, or can be in its interior. Our results include bit complexity bounds, a novel general hardness construction, and a polynomial-time approximation scheme. We fully characterize the situation in 2D, and provide first results in dimensions 3 and higher for several versions of the problem.
Concretely, our results resolve several open problems. We prove that computing the minimum-link diffuse reflection path, motivated by ray tracing in computer graphics, is NP-hard, even for two-dimensional polygonal domains with holes. This has remained an open problem [Ghosh et al. 2012] despite a large body of work on the topic. We also resolve the open problem from [Mitchell et al. 1992] mentioned in the handbook [Goodman and O'Rourke, 2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [Demaine et al. TOPP] (see Problem 22): "What is the complexity of the minimum-link path problem in 3-space?" Our results imply that the problem is NP-hard even on terrains (and hence, due to discreteness of the answer, there is no FPTAS unless P=NP), but admits a PTAS.
Cite as
Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals. On the Complexity of Minimum-Link Path Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{kostitsyna_et_al:LIPIcs.SoCG.2016.49,
author = {Kostitsyna, Irina and L\"{o}ffler, Maarten and Polishchuk, Valentin and Staals, Frank},
title = {{On the Complexity of Minimum-Link Path Problems}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {49:1--49:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.49},
URN = {urn:nbn:de:0030-drops-59412},
doi = {10.4230/LIPIcs.SoCG.2016.49},
annote = {Keywords: minimum-linkpath, diffuse reflection, terrain, bit complexity, NP-hardness}
}
Document
A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino
Abstract
A plane tiling consisting of congruent copies of a shape is isohedral provided that for any pair of copies, there exists a symmetry of the tiling mapping one copy to the other. We give a O(n*log^2(n))-time algorithm for deciding if a polyomino with n edges can tile the plane isohedrally. This improves on the O(n^{18})-time algorithm of Keating and Vince and generalizes recent work by Brlek, Provençal, Fédou, and the second author.
Cite as
Stefan Langerman and Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{langerman_et_al:LIPIcs.SoCG.2016.50,
author = {Langerman, Stefan and Winslow, Andrew},
title = {{A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {50:1--50:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.50},
URN = {urn:nbn:de:0030-drops-59423},
doi = {10.4230/LIPIcs.SoCG.2016.50},
annote = {Keywords: Plane tiling, polyomino, boundary word, isohedral}
}
Document
Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the r-Metastable Range
Abstract
Motivated by Tverberg-type problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into R^d without higher-multiplicity intersections.
We focus on conditions for the existence of almost r-embeddings, i.e., maps f: K -> R^d such that the intersection of f(sigma_1), ..., f(sigma_r) is empty whenever sigma_1,...,sigma_r are pairwise disjoint simplices of K.
Generalizing the classical Haefliger-Weber embeddability criterion, we show that a well-known necessary deleted product condition for the existence of almost r-embeddings is sufficient in a suitable r-metastable range of dimensions: If r d > (r+1) dim K + 2 then there exists an almost r-embedding K-> R^d if and only if there exists an equivariant map of the r-fold deleted product of K to the sphere S^(d(r-1)-1).
This significantly extends one of the main results of our previous paper (which treated the special case where d=rk and dim K=(r-1)k, for some k> 2), and settles an open question raised there.
Cite as
Isaac Mabillard and Uli Wagner. Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the r-Metastable Range. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{mabillard_et_al:LIPIcs.SoCG.2016.51,
author = {Mabillard, Isaac and Wagner, Uli},
title = {{Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the r-Metastable Range}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {51:1--51:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.51},
URN = {urn:nbn:de:0030-drops-59438},
doi = {10.4230/LIPIcs.SoCG.2016.51},
annote = {Keywords: Topological Combinatorics, Tverberg-Type Problems, Simplicial Complexes, Piecewise-Linear Topology, Haefliger-Weber Theorem}
}
Document
Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
Abstract
Given a set of n points S in the plane, a triangulation T of S is a maximal set of non-crossing segments with endpoints in S. We present an algorithm that computes the number of triangulations on a given set of n points in time n^{ (11+ o(1)) sqrt{n} }, significantly improving the previous best running time of O(2^n n^2) by Alvarez and Seidel [SoCG 2013]. Our main tool is identifying separators of size O(sqrt{n}) of a triangulation in a canonical way. The definition of the separators are based on the decomposition of the triangulation into nested layers ("cactus graphs"). Based on the above algorithm, we develop a simple and formal framework to count other non-crossing straight-line graphs in n^{O(sqrt{n})} time. We demonstrate the usefulness of the framework by applying it to counting non-crossing Hamilton cycles, spanning trees, perfect matchings, 3-colorable triangulations, connected graphs, cycle decompositions, quadrangulations, 3-regular graphs, and more.
Cite as
Dániel Marx and Tillmann Miltzow. Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{marx_et_al:LIPIcs.SoCG.2016.52,
author = {Marx, D\'{a}niel and Miltzow, Tillmann},
title = {{Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {52:1--52:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.52},
URN = {urn:nbn:de:0030-drops-59445},
doi = {10.4230/LIPIcs.SoCG.2016.52},
annote = {Keywords: computational geometry, triangulations, exponential-time algorithms}
}
Document
Convergence between Categorical Representations of Reeb Space and Mapper
Abstract
The Reeb space, which generalizes the notion of a Reeb graph, is one of the few tools in topological data analysis and visualization suitable for the study of multivariate scientific datasets. First introduced by Edelsbrunner et al., it compresses the components of the level sets of a multivariate mapping and obtains a summary representation of their relationships. A related construction called mapper, and a special case of the mapper construction called the Joint Contour Net have been shown to be effective in visual analytics. Mapper and JCN are intuitively regarded as discrete approximations of the Reeb space, however without formal proofs or approximation guarantees. An open question has been proposed by Dey et al. as to whether the mapper construction converges to the Reeb space in the limit.
In this paper, we are interested in developing the theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis. Using tools from category theory, we formally prove the convergence between the Reeb space and mapper in terms of an interleaving distance between their categorical representations. Given a sequence of refined discretizations, we prove that these approximations converge to the Reeb space in the interleaving distance; this also helps to quantify the approximation quality of the discretization at a fixed resolution.
Cite as
Elizabeth Munch and Bei Wang. Convergence between Categorical Representations of Reeb Space and Mapper. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{munch_et_al:LIPIcs.SoCG.2016.53,
author = {Munch, Elizabeth and Wang, Bei},
title = {{Convergence between Categorical Representations of Reeb Space and Mapper}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {53:1--53:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.53},
URN = {urn:nbn:de:0030-drops-59454},
doi = {10.4230/LIPIcs.SoCG.2016.53},
annote = {Keywords: Topological data analysis, Reeb space, mapper, category theory}
}
Document
New Lower Bounds for epsilon-Nets
Abstract
Following groundbreaking work by Haussler and Welzl (1987), the use of small epsilon-nets has become a standard technique for solving algorithmic and extremal problems in geometry and learning theory. Two significant recent developments are: (i) an upper bound on the size of the smallest epsilon-nets for set systems, as a function of their so-called shallow-cell complexity (Chan, Grant, Konemann, and Sharpe); and (ii) the construction of a set system whose members can be obtained by intersecting a point set in R^4 by a family of half-spaces such that the size of any epsilon-net for them is at least (1/(9*epsilon)) log (1/epsilon) (Pach and Tardos).
The present paper completes both of these avenues of research. We (i) give a lower bound, matching the result of Chan et al., and (ii) generalize the construction of Pach and Tardos to half-spaces in R^d, for any d >= 4, to show that the general upper bound of Haussler and Welzl for the size of the smallest epsilon-nets is tight.
Cite as
Andrey Kupavskii, Nabil Mustafa, and János Pach. New Lower Bounds for epsilon-Nets. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{kupavskii_et_al:LIPIcs.SoCG.2016.54,
author = {Kupavskii, Andrey and Mustafa, Nabil and Pach, J\'{a}nos},
title = {{New Lower Bounds for epsilon-Nets}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {54:1--54:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.54},
URN = {urn:nbn:de:0030-drops-59467},
doi = {10.4230/LIPIcs.SoCG.2016.54},
annote = {Keywords: epsilon-nets; lower bounds; geometric set systems; shallow-cell complexity; half-spaces}
}
Document
On Computing the Fréchet Distance Between Surfaces
Abstract
We describe two (1+epsilon)-approximation algorithms for computing the Fréchet distance between two homeomorphic piecewise linear surfaces R and S of genus zero and total complexity n, with Frechet distance delta.
(1) A 2^{O((n + ( (Area(R)+Area(S))/(epsilon.delta)^2 )^2 )} time algorithm if R and S are composed of fat triangles (triangles with angles larger than a constant).
(2) An O(D/(epsilon.delta)^2) n + 2^{O(D^4/(epsilon^4.delta^2))} time algorithm if R and S are polyhedral terrains over [0,1]^2 with slope at most D.
Although, the Fréchet distance between curves has been studied extensively, very little is known for surfaces. Our results are the first algorithms (both for surfaces and terrains) that are guaranteed to terminate in finite time. Our latter result, in particular, implies a linear time algorithm for terrains of constant maximum slope and constant Frechet distance.
Cite as
Amir Nayyeri and Hanzhong Xu. On Computing the Fréchet Distance Between Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{nayyeri_et_al:LIPIcs.SoCG.2016.55,
author = {Nayyeri, Amir and Xu, Hanzhong},
title = {{On Computing the Fr\'{e}chet Distance Between Surfaces}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {55:1--55:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.55},
URN = {urn:nbn:de:0030-drops-59471},
doi = {10.4230/LIPIcs.SoCG.2016.55},
annote = {Keywords: Surfaces, Terrains, Frechet distance, Parametrized complexity, normal coordinates}
}
Document
The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon
Abstract
Given a set of sites (points) in a simple polygon, the farthest-point geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n+m)loglogn)-time algorithm to compute the farthest-point geodesic Voronoi diagram for m sites lying on the boundary of a simple n-gon.
Cite as
Eunjin Oh, Luis Barba, and Hee-Kap Ahn. The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{oh_et_al:LIPIcs.SoCG.2016.56,
author = {Oh, Eunjin and Barba, Luis and Ahn, Hee-Kap},
title = {{The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {56:1--56:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.56},
URN = {urn:nbn:de:0030-drops-59481},
doi = {10.4230/LIPIcs.SoCG.2016.56},
annote = {Keywords: Geodesic distance, simple polygons, farthest-point Voronoi diagram}
}
Document
Avoiding the Global Sort: A Faster Contour Tree Algorithm
Abstract
We revisit the classical problem of computing the contour tree of a scalar field f:M to R, where M is a triangulated simplicial mesh in R^d. The contour tree is a fundamental topological structure that tracks the evolution of level sets of f and has numerous applications in data analysis and visualization.
All existing algorithms begin with a global sort of at least all critical values of f, which can require (roughly) Omega(n log n) time. Existing lower bounds show that there are pathological instances where this sort is required. We present the first algorithm whose time complexity depends on the contour tree structure, and avoids the global sort for non-pathological inputs. If C denotes the set of critical points in M, the running time is roughly O(sum_{v in C} log l_v), where l_v is the depth of v in the contour tree. This matches all existing upper bounds, but is a significant asymptotic improvement when the contour tree is short and fat. Specifically, our approach ensures that any comparison made is between nodes that are either adjacent in M or in the same descending path in the contour tree, allowing us to argue strong optimality properties of our algorithm.
Our algorithm requires several novel ideas: partitioning M in well-behaved portions, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis.
Cite as
Benjamin Raichel and C. Seshadhri. Avoiding the Global Sort: A Faster Contour Tree Algorithm. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{raichel_et_al:LIPIcs.SoCG.2016.57,
author = {Raichel, Benjamin and Seshadhri, C.},
title = {{Avoiding the Global Sort: A Faster Contour Tree Algorithm}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {57:1--57:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.57},
URN = {urn:nbn:de:0030-drops-59490},
doi = {10.4230/LIPIcs.SoCG.2016.57},
annote = {Keywords: contour trees, computational topology, computational geometry}
}
Document
Configurations of Lines in 3-Space and Rigidity of Planar Structures
Abstract
Let L be a sequence (l_1,l_2,...,l_n) of n lines in C^3. We define the intersection graph G_L=([n],E) of L, where [n]:={1,..., n}, and with {i,j} in E if and only if i\neq j and the corresponding lines l_i and l_j intersect, or are parallel (or coincide). For a graph G=([n],E), we say that a sequence L is a realization of G if G subset G_L. One of the main results of this paper is to provide a combinatorial characterization of graphs G=([n],E) that have the following property: For every generic realization L of G, that consists of n pairwise distinct lines, we have G_L=K_n, in which case the lines of L are either all concurrent or all coplanar.
The general statements that we obtain about lines, apart from their independent interest, turns out to be closely related to the notion of graph rigidity. The connection is established due to the so-called Elekes-Sharir framework, which allows us to transform the problem into an incidence problem involving lines in three dimensions. By exploiting the geometry of contacts between lines in 3D, we can obtain alternative, simpler, and more precise characterizations of the rigidity of graphs.
Cite as
Orit E. Raz. Configurations of Lines in 3-Space and Rigidity of Planar Structures. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{raz:LIPIcs.SoCG.2016.58,
author = {Raz, Orit E.},
title = {{Configurations of Lines in 3-Space and Rigidity of Planar Structures}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {58:1--58:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.58},
URN = {urn:nbn:de:0030-drops-59503},
doi = {10.4230/LIPIcs.SoCG.2016.58},
annote = {Keywords: Line configurations, Rigidity, Global Rigidity, Laman graphs}
}
Document
Weak 1/r-Nets for Moving Points
Abstract
In this paper, we extend the weak 1/r-net theorem to a kinetic setting where the underlying set of points is moving polynomially with bounded description complexity. We establish that one can find a kinetic analog N of a weak 1/r-net of cardinality O(r^(d(d+1)/2)log^d r) whose points are moving with coordinates that are rational functions with bounded description complexity. Moreover, each member of N has one polynomial coordinate.
Cite as
Alexandre Rok and Shakhar Smorodinsky. Weak 1/r-Nets for Moving Points. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{rok_et_al:LIPIcs.SoCG.2016.59,
author = {Rok, Alexandre and Smorodinsky, Shakhar},
title = {{Weak 1/r-Nets for Moving Points}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {59:1--59:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.59},
URN = {urn:nbn:de:0030-drops-59514},
doi = {10.4230/LIPIcs.SoCG.2016.59},
annote = {Keywords: Hypergraphs, Weak epsilon-net}
}
Document
Applications of Incidence Bounds in Point Covering Problems
Abstract
In the Line Cover problem a set of n points is given and the task is to cover the points using either the minimum number of lines or at most k lines. In Curve Cover, a generalization of Line Cover, the task is to cover the points using curves with d degrees of freedom. Another generalization is the Hyperplane Cover problem where points in d-dimensional space are to be covered by hyperplanes. All these problems have kernels of polynomial size, where the parameter is the minimum number of lines, curves, or hyperplanes needed.
First we give a non-parameterized algorithm for both problems in O*(2^n) (where the O*(.) notation hides polynomial factors of n) time and polynomial space, beating a previous exponential-space result. Combining this with incidence bounds similar to the famous Szemeredi-Trotter bound, we present a Curve Cover algorithm with running time O*((Ck/log k)^((d-1)k)), where C is some constant. Our result improves the previous best times O*((k/1.35)^k) for Line Cover (where d=2), O*(k^(dk)) for general Curve Cover, as well as a few other bounds for covering points by parabolas or conics. We also present an algorithm for Hyperplane Cover in R^3 with running time O*((Ck^2/log^(1/5) k)^k), improving on the previous time of O*((k^2/1.3)^k).
Cite as
Peyman Afshani, Edvin Berglin, Ingo van Duijn, and Jesper Sindahl Nielsen. Applications of Incidence Bounds in Point Covering Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{afshani_et_al:LIPIcs.SoCG.2016.60,
author = {Afshani, Peyman and Berglin, Edvin and van Duijn, Ingo and Sindahl Nielsen, Jesper},
title = {{Applications of Incidence Bounds in Point Covering Problems}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {60:1--60:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.60},
URN = {urn:nbn:de:0030-drops-59527},
doi = {10.4230/LIPIcs.SoCG.2016.60},
annote = {Keywords: Point Cover, Incidence Bounds, Inclusion Exclusion, Exponential Algorithm}
}
Document
Grouping Time-Varying Data for Interactive Exploration
Abstract
We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of time-varying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: group-size, group-duration, and inter-entity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an output-sensitive manner. Our results hold in R^d for fixed d.
Cite as
Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Grouping Time-Varying Data for Interactive Exploration. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{vangoethem_et_al:LIPIcs.SoCG.2016.61,
author = {van Goethem, Arthur and van Kreveld, Marc and L\"{o}ffler, Maarten and Speckmann, Bettina and Staals, Frank},
title = {{Grouping Time-Varying Data for Interactive Exploration}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {61:1--61:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.61},
URN = {urn:nbn:de:0030-drops-59539},
doi = {10.4230/LIPIcs.SoCG.2016.61},
annote = {Keywords: Trajectory, Time series, Moving entity, Grouping, Algorithm, Data structure}
}
Document
On the Separability of Stochastic Geometric Objects, with Applications
Abstract
In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint/multipoint uncertainty models. Let S=S_R U S_B be a given set of stochastic bichromatic points, and define n = min{|S_R|, |S_B|} and N = max{|S_R|, |S_B|}. We show that the separable-probability (SP) of S can be computed in O(nN^{d-1}) time for d >= 3 and O(min{nN log N, N^2}) time for d=2, while the expected separation-margin (ESM) of S can be computed in O(nN^d) time for d >= 2. In addition, we give an Omega(nN^{d-1}) witness-based lower bound for computing SP, which implies the optimality of our algorithm among all those in this category. Also, a hardness result for computing ESM is given to show the difficulty of further improving our algorithm. As an extension, we generalize the same problems from points to general geometric objects, i.e., polytopes and/or balls, and extend our algorithms to solve the generalized SP and ESM problems in O(nN^d) and O(nN^{d+1}) time, respectively. Finally, we present some applications of our algorithms to stochastic convex-hull related problems.
Cite as
Jie Xue, Yuan Li, and Ravi Janardan. On the Separability of Stochastic Geometric Objects, with Applications. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{xue_et_al:LIPIcs.SoCG.2016.62,
author = {Xue, Jie and Li, Yuan and Janardan, Ravi},
title = {{On the Separability of Stochastic Geometric Objects, with Applications}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {62:1--62:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.62},
URN = {urn:nbn:de:0030-drops-59544},
doi = {10.4230/LIPIcs.SoCG.2016.62},
annote = {Keywords: Stochastic objects, linear separability, separable-probability, expected separation-margin, convex hull}
}
Document
Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties
Abstract
The symmetric difference is a robust operator for measuring the error of approximating one shape by another. Given two convex shapes P and C, we study the problem of minimizing the volume of their symmetric difference under all possible scalings and translations of C. We prove that the problem can be solved by convex programming. We also present a combinatorial algorithm for convex polygons in the plane that runs in O((m+n) log^3(m+n)) expected time, where n and m denote the number of vertices of P and C, respectively.
Cite as
Juyoung Yon, Sang Won Bae, Siu-Wing Cheng, Otfried Cheong, and Bryan T. Wilkinson. Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{yon_et_al:LIPIcs.SoCG.2016.63,
author = {Yon, Juyoung and Bae, Sang Won and Cheng, Siu-Wing and Cheong, Otfried and Wilkinson, Bryan T.},
title = {{Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {63:1--63:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.63},
URN = {urn:nbn:de:0030-drops-59551},
doi = {10.4230/LIPIcs.SoCG.2016.63},
annote = {Keywords: shape matching, convexity, symmetric difference, homotheties}
}
Document
Interactive Geometric Algorithm Visualization in a Browser
Abstract
We present an online, interactive tool for writing and presenting interactive geometry demos suitable for classroom demonstrations. Code for the demonstrations is written in JavaScript using p5.js, a JavaScript library based on Processing.
Cite as
Kirk Gardner, Lynn Asselin, and Donald Sheehy. Interactive Geometric Algorithm Visualization in a Browser. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 64:1-64:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{gardner_et_al:LIPIcs.SoCG.2016.64,
author = {Gardner, Kirk and Asselin, Lynn and Sheehy, Donald},
title = {{Interactive Geometric Algorithm Visualization in a Browser}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {64:1--64:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.64},
URN = {urn:nbn:de:0030-drops-59563},
doi = {10.4230/LIPIcs.SoCG.2016.64},
annote = {Keywords: Computational Geometry, Processing, JavaScript, Visualisation, Incremental Algorithms}
}
Document
Geometric Models for Musical Audio Data
Abstract
We study the geometry of sliding window embeddings of audio features that summarize perceptual information about audio, including its pitch and timbre. These embeddings can be viewed as point clouds in high dimensions, and we add structure to the point clouds using a cover tree with adaptive thresholds based on multi-scale local principal component analysis to automatically assign points to clusters. We connect neighboring clusters in a scaffolding graph, and we use knowledge of stratified space structure to refine our estimates of dimension in each cluster, demonstrating in our music applications that choruses and verses have higher dimensional structure, while transitions between them are lower dimensional. We showcase our technique with an interactive web-based application powered by Javascript and WebGL which plays music synchronized with a principal component analysis embedding of the point cloud down to 3D. We also render the clusters and the scaffolding on top of this projection to visualize the transitions between different sections of the music.
Cite as
Paul Bendich, Ellen Gasparovic, John Harer, and Christopher Tralie. Geometric Models for Musical Audio Data. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 65:1-65:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bendich_et_al:LIPIcs.SoCG.2016.65,
author = {Bendich, Paul and Gasparovic, Ellen and Harer, John and Tralie, Christopher},
title = {{Geometric Models for Musical Audio Data}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {65:1--65:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.65},
URN = {urn:nbn:de:0030-drops-59577},
doi = {10.4230/LIPIcs.SoCG.2016.65},
annote = {Keywords: Geometric Models, Audio Analysis, High Dimensional Data Analysis, Stratified Space Models}
}
Document
Visualizing Scissors Congruence
Abstract
Consider two simple polygons with equal area. The Wallace-Bolyai-Gerwien theorem states that these polygons are scissors congruent, that is, they can be dissected into finitely many congruent polygonal pieces. We present an interactive application that visualizes this constructive proof.
Cite as
Satyan Devadoss, Ziv Epstein, and Dmitriy Smirnov. Visualizing Scissors Congruence. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 66:1-66:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{devadoss_et_al:LIPIcs.SoCG.2016.66,
author = {Devadoss, Satyan and Epstein, Ziv and Smirnov, Dmitriy},
title = {{Visualizing Scissors Congruence}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {66:1--66:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.66},
URN = {urn:nbn:de:0030-drops-59585},
doi = {10.4230/LIPIcs.SoCG.2016.66},
annote = {Keywords: polygonal congruence, geometry, rigid transformations}
}
Document
Visualization of Geometric Spanner Algorithms
Abstract
It is easier to understand an algorithm when it can be seen in interactive mode. The current study implemented four algorithms to construct geometric spanners; the path-greedy, gap-greedy, Theta-graph and Yao-graph algorithms. The data structure visualization framework (http://www.cs.usfca.edu/~galles/visualization/) developed by David Galles was used.
Two features were added to allow its use in spanner algorithm visualization: support point-based algorithms and export of the output to Ipe drawing software format. The interactive animations in the framework make steps of visualization beautiful and media controls are available to manage the animations. Visualization does not require extensions to be installed on the web browser. It is available at http://cs.yazd.ac.ir/cgalg/AlgsVis/.
Cite as
Mohammad Farshi and Seyed Hossein Hosseini. Visualization of Geometric Spanner Algorithms. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 67:1-67:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{farshi_et_al:LIPIcs.SoCG.2016.67,
author = {Farshi, Mohammad and Hosseini, Seyed Hossein},
title = {{Visualization of Geometric Spanner Algorithms}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {67:1--67:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.67},
URN = {urn:nbn:de:0030-drops-59594},
doi = {10.4230/LIPIcs.SoCG.2016.67},
annote = {Keywords: geometric spanner networks, geometric spanner algorithms animations.}
}
Document
Path Planning for Simple Robots using Soft Subdivision Search
Abstract
The concept of resolution-exact path planning is a theoretically sound alternative to the standard exact algorithms, and provides much stronger guarantees than probabilistic or sampling algorithms. It opens the way for the introduction of soft predicates in the context of subdivision algorithm. Taking a leaf from the great success of the Probabilistic Road Map (PRM) framework, we formulate an analogous framework for subdivision, called Soft Subdivision Search (SSS). In this video, we illustrate the SSS framework for a trio of simple planar robots: disc, triangle and 2-links. These robots have, respectively, 2, 3 and 4 degrees of freedom. Our 2-link robot can also avoid self-crossing. These algorithms operate in realtime and are relatively easy to implement.
Cite as
Ching-Hsiang Hsu, John Paul Ryan, and Chee Yap. Path Planning for Simple Robots using Soft Subdivision Search. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 68:1-68:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{hsu_et_al:LIPIcs.SoCG.2016.68,
author = {Hsu, Ching-Hsiang and Ryan, John Paul and Yap, Chee},
title = {{Path Planning for Simple Robots using Soft Subdivision Search}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {68:1--68:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.68},
URN = {urn:nbn:de:0030-drops-59607},
doi = {10.4230/LIPIcs.SoCG.2016.68},
annote = {Keywords: Robot Path Planning, Soft Predicates, Resolution-Exact Algorithm, Subdivision Search}
}
Document
Exploring Circle Packing Algorithms
Abstract
We present an interactive tool for visualizing and experimenting with different circle packing algorithms.
Cite as
Kevin Pratt, Connor Riley, and Donald Sheehy. Exploring Circle Packing Algorithms. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 69:1-69:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{pratt_et_al:LIPIcs.SoCG.2016.69,
author = {Pratt, Kevin and Riley, Connor and Sheehy, Donald},
title = {{Exploring Circle Packing Algorithms}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {69:1--69:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.69},
URN = {urn:nbn:de:0030-drops-59616},
doi = {10.4230/LIPIcs.SoCG.2016.69},
annote = {Keywords: Computational Geometry, Processing, Javascript, Visualization, Incremental Algorithms}
}
Document
The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation
Abstract
We describe and demonstrate the Explicit Corridor Map (ECM), a navigation mesh for path planning and crowd simulation in virtual environments. For a bounded 2D environment with polygonal obstacles, the ECM is the medial axis of the free space annotated with nearest-obstacle information. It can be used to compute short and smooth paths for disk-shaped characters of any radius. It is also well-defined for multi-layered 3D environments that consist of connected planar layers. We highlight various operations on the ECM, such as dynamic updates, visibility queries, and the computation of paths (indicative routes).
We have implemented the ECM as the basis of a real-time crowd simulation framework with path following and collision avoidance. Our implementation has been successfully used to simulate real-life events involving large crowds of heterogeneous characters. The enclosed demo application displays various features of our software.
Cite as
Wouter van Toll, Atlas F. Cook IV, Marc van Kreveld, and Roland Geraerts. The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 70:1-70:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{vantoll_et_al:LIPIcs.SoCG.2016.70,
author = {van Toll, Wouter and Cook IV, Atlas F. and van Kreveld, Marc and Geraerts, Roland},
title = {{The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {70:1--70:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.70},
URN = {urn:nbn:de:0030-drops-59622},
doi = {10.4230/LIPIcs.SoCG.2016.70},
annote = {Keywords: Medial axis, Navigation mesh, Path planning, Crowd simulation}
}
Document
High-Dimensional Geometry of Sliding Window Embeddings of Periodic Videos
Abstract
We explore the high dimensional geometry of sliding windows of periodic videos. Under a reasonable model for periodic videos, we show that the sliding window is necessary to disambiguate all states within a period, and we show that a video embedding with a sliding window of an appropriate dimension lies on a topological loop along a hypertorus. This hypertorus has an independent ellipse for each harmonic of the motion. Natural motions with sharp transitions from foreground to background have many harmonics and are hence in higher dimensions, so linear subspace projections such as PCA do not accurately summarize the geometry of these videos. Noting this, we invoke tools from topological data analysis and cohomology to parameterize motions in high dimensions with circular coordinates after the embeddings. We show applications to videos in which there is obvious periodic motion and to videos in which the motion is hidden.
Cite as
Christopher Tralie. High-Dimensional Geometry of Sliding Window Embeddings of Periodic Videos. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 71:1-71:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{tralie:LIPIcs.SoCG.2016.71,
author = {Tralie, Christopher},
title = {{High-Dimensional Geometry of Sliding Window Embeddings of Periodic Videos}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {71:1--71:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.71},
URN = {urn:nbn:de:0030-drops-59630},
doi = {10.4230/LIPIcs.SoCG.2016.71},
annote = {Keywords: Video Processing, High Dimensional Geometry, Circular Coordinates, Nonlinear Time Series}
}
Document
Introduction to Persistent Homology
Abstract
This video presents an introduction to persistent homology, aimed at a viewer who has mathematical aptitude but not necessarily knowledge of algebraic topology. Persistent homology is an algebraic method of discerning the topological features of complex data, which in recent years has found applications in fields such as image processing and biological systems. Using smooth animations, the video conveys the intuition behind persistent homology, while giving a taste of its key properties, applications, and mathematical underpinnings.
Cite as
Matthew L. Wright. Introduction to Persistent Homology. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 72:1-72:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{wright:LIPIcs.SoCG.2016.72,
author = {Wright, Matthew L.},
title = {{Introduction to Persistent Homology}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {72:1--72:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {Fekete, S\'{a}ndor and Lubiw, Anna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.72},
URN = {urn:nbn:de:0030-drops-59643},
doi = {10.4230/LIPIcs.SoCG.2016.72},
annote = {Keywords: Persistent Homology, Topological Data Analysi}
}