Document

**Published in:** LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in a d-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map on the sphere of directions S^(d-1). We show that the combinatorial complexity of the Gaussian map for the order-k Voronoi diagram of n line segments or lines is O(min{k,n-k} n^(d-1)), which is tight for n-k = O(1). All the d-dimensional cells of the farthest Voronoi diagram are unbounded, its (d-1)-skeleton is connected, and it does not have tunnels. A d-cell of the Voronoi diagram is called a tunnel if the set of its unbounded directions, represented as points on its Gaussian map, is not connected. In a three-dimensional space, the farthest Voronoi diagram of lines has exactly n^2-n three-dimensional cells, when n >= 2. The Gaussian map of the farthest Voronoi diagram of line segments or lines can be constructed in O(n^(d-1) alpha(n)) time, while if d=3, the time drops to worst-case optimal O(n^2).

Gill Barequet, Evanthia Papadopoulou, and Martin Suderland. Unbounded Regions of High-Order Voronoi Diagrams of Lines and Segments in Higher Dimensions. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.ISAAC.2019.62, author = {Barequet, Gill and Papadopoulou, Evanthia and Suderland, Martin}, title = {{Unbounded Regions of High-Order Voronoi Diagrams of Lines and Segments in Higher Dimensions}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {62:1--62:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.62}, URN = {urn:nbn:de:0030-drops-115582}, doi = {10.4230/LIPIcs.ISAAC.2019.62}, annote = {Keywords: Voronoi diagram, lines, line segments, higher-order, order-k, unbounded, hypersphere arrangement, great hyperspheres} }

Document

Complete Volume

**Published in:** LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

LIPIcs, Volume 129, SoCG'19, Complete Volume

35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{barequet_et_al:LIPIcs.SoCG.2019, title = {{LIPIcs, Volume 129, SoCG'19, Complete Volume}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019}, URN = {urn:nbn:de:0030-drops-105562}, doi = {10.4230/LIPIcs.SoCG.2019}, annote = {Keywords: Theory of computation, Computational geometry, Design and analysis of algorithms, Mathematics of computing, Combinatorics, Graph algortihms} }

Document

Front Matter

**Published in:** LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Front Matter, Table of Contents, Preface, Conference Organization

35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.SoCG.2019.0, author = {Barequet, Gill and Wang, Yusu}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.0}, URN = {urn:nbn:de:0030-drops-104047}, doi = {10.4230/LIPIcs.SoCG.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }

Document

Multimedia Exposition

**Published in:** LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

In this video, we survey some results concerning polyominoes, which are sets of connected cells on the square lattice, and specifically, minimal-perimeter polyominoes, that are polyominoes with the minimal-perimeter from all polyominoes of the same size.

Gill Barequet and Gil Ben-Shachar. Properties of Minimal-Perimeter Polyominoes (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 64:1-64:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.SoCG.2019.64, author = {Barequet, Gill and Ben-Shachar, Gil}, title = {{Properties of Minimal-Perimeter Polyominoes}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {64:1--64:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.64}, URN = {urn:nbn:de:0030-drops-104687}, doi = {10.4230/LIPIcs.SoCG.2019.64}, annote = {Keywords: Polyominoes, Perimeter, Minimal-Perimeter} }

Document

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

We study algorithms and combinatorial complexity bounds for stable-matching Voronoi diagrams, where a set, S, of n point sites in the plane determines a stable matching between the points in R^2 and the sites in S such that (i) the points prefer sites closer to them and sites prefer points closer to them, and (ii) each site has a quota indicating the area of the set of points that can be matched to it. Thus, a stable-matching Voronoi diagram is a solution to the classic post office problem with the added (realistic) constraint that each post office has a limit on the size of its jurisdiction. Previous work provided existence and uniqueness proofs, but did not analyze its combinatorial or algorithmic complexity. We show that a stable-matching Voronoi diagram of n sites has O(n^{2+epsilon}) faces and edges, for any epsilon>0, and show that this bound is almost tight by giving a family of diagrams with Theta(n^2) faces and edges. We also provide a discrete algorithm for constructing it in O(n^3+n^2f(n)) time, where f(n) is the runtime of a geometric primitive that can be performed in the real-RAM model or can be approximated numerically. This is necessary, as the diagram cannot be computed exactly in an algebraic model of computation.

Gill Barequet, David Eppstein, Michael T. Goodrich, and Nil Mamano. Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.ICALP.2018.89, author = {Barequet, Gill and Eppstein, David and Goodrich, Michael T. and Mamano, Nil}, title = {{Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {89:1--89:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.89}, URN = {urn:nbn:de:0030-drops-90937}, doi = {10.4230/LIPIcs.ICALP.2018.89}, annote = {Keywords: Voronoi diagram, stable matching, combinatorial complexity, lower bounds} }

Document

**Published in:** LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

This video describes a general framework for computing formulae enumerating polycubes of size n which are proper in n-k dimensions (i.e., spanning all n-k dimensions), for a fixed value of k. (Such formulae are central in the literature of statistical physics in the study of percolation processes and collapse of branched polymers.) The implemented software re-affirmed the already-proven formulae for k <= 3, and proved rigorously, for the first time, the formula enumerating polycubes of size n that are proper in n-4 dimensions.

Gill Barequet and Mira Shalah. Automatic Proofs for Formulae Enumerating Proper Polycubes. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 19-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.SOCG.2015.19, author = {Barequet, Gill and Shalah, Mira}, title = {{Automatic Proofs for Formulae Enumerating Proper Polycubes}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {19--22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.19}, URN = {urn:nbn:de:0030-drops-50889}, doi = {10.4230/LIPIcs.SOCG.2015.19}, annote = {Keywords: Polycubes, inclusion-exclusion} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail