LIPIcs, Volume 129
SoCG 2019, June 18-21, 2019, Portland, Oregon, USA
Editors: Gill Barequet and Yusu Wang
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
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)
@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} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@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} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
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)
@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} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Sanjoy Dasgupta. A Geometric Data Structure from Neuroscience (Invited Talk). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dasgupta:LIPIcs.SoCG.2019.1, author = {Dasgupta, Sanjoy}, title = {{A Geometric Data Structure from Neuroscience}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.1}, URN = {urn:nbn:de:0030-drops-104055}, doi = {10.4230/LIPIcs.SoCG.2019.1}, annote = {Keywords: Geometric data structure, algorithm design, neuroscience} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Bruce R. Donald. Some Geometric and Computational Challenges Arising in Structural Molecular Biology (Invited Talk). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{donald:LIPIcs.SoCG.2019.2, author = {Donald, Bruce R.}, title = {{Some Geometric and Computational Challenges Arising in Structural Molecular Biology}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {2:1--2:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.2}, URN = {urn:nbn:de:0030-drops-104065}, doi = {10.4230/LIPIcs.SoCG.2019.2}, annote = {Keywords: Geometric computing, combutational biology, Continuous Interdomain Orientation Distributions of Protein Conformations} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Peyman Afshani. A New Lower Bound for Semigroup Orthogonal Range Searching. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{afshani:LIPIcs.SoCG.2019.3, author = {Afshani, Peyman}, title = {{A New Lower Bound for Semigroup Orthogonal Range Searching}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {3:1--3:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.3}, URN = {urn:nbn:de:0030-drops-104075}, doi = {10.4230/LIPIcs.SoCG.2019.3}, annote = {Keywords: Data Structures, Range Searching, Lower bounds} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Peyman Afshani and Jeff M. Phillips. Independent Range Sampling, Revisited Again. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{afshani_et_al:LIPIcs.SoCG.2019.4, author = {Afshani, Peyman and Phillips, Jeff M.}, title = {{Independent Range Sampling, Revisited Again}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {4:1--4:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.4}, URN = {urn:nbn:de:0030-drops-104088}, doi = {10.4230/LIPIcs.SoCG.2019.4}, annote = {Keywords: Range Searching, Data Structures, Sampling} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Pankaj K. Agarwal, Boris Aronov, Esther Ezra, and Joshua Zahl. An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.5, author = {Agarwal, Pankaj K. and Aronov, Boris and Ezra, Esther and Zahl, Joshua}, title = {{An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {5:1--5:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.5}, URN = {urn:nbn:de:0030-drops-104096}, doi = {10.4230/LIPIcs.SoCG.2019.5}, annote = {Keywords: Polynomial partitioning, quantifier elimination, semi-algebraic range spaces, epsilon-samples} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Pankaj K. Agarwal, Hsien-Chih Chang, and Allen Xiao. Efficient Algorithms for Geometric Partial Matching. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.6, author = {Agarwal, Pankaj K. and Chang, Hsien-Chih and Xiao, Allen}, title = {{Efficient Algorithms for Geometric Partial Matching}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.6}, URN = {urn:nbn:de:0030-drops-104109}, doi = {10.4230/LIPIcs.SoCG.2019.6}, annote = {Keywords: partial matching, transportation, optimal transport, minimum-cost flow, bichromatic closest pair} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Akanksha Agrawal, Grzegorz Guśpiel, Jayakrishnan Madathil, Saket Saurabh, and Meirav Zehavi. Connecting the Dots (with Minimum Crossings). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agrawal_et_al:LIPIcs.SoCG.2019.7, author = {Agrawal, Akanksha and Gu\'{s}piel, Grzegorz and Madathil, Jayakrishnan and Saurabh, Saket and Zehavi, Meirav}, title = {{Connecting the Dots (with Minimum Crossings)}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.7}, URN = {urn:nbn:de:0030-drops-104117}, doi = {10.4230/LIPIcs.SoCG.2019.7}, annote = {Keywords: crossing minimization, parameterized complexity, FPT algorithm, polynomial kernel, W\lbrack1\rbrack-hardness} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Dror Aiger, Haim Kaplan, Efi Kokiopoulou, Micha Sharir, and Bernhard Zeisl. General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{aiger_et_al:LIPIcs.SoCG.2019.8, author = {Aiger, Dror and Kaplan, Haim and Kokiopoulou, Efi and Sharir, Micha and Zeisl, Bernhard}, title = {{General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.8}, URN = {urn:nbn:de:0030-drops-104129}, doi = {10.4230/LIPIcs.SoCG.2019.8}, annote = {Keywords: Camera positioning, Approximate incidences, Incidences} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, and Csaba D. Tóth. Circumscribing Polygons and Polygonizations for Disjoint Line Segments. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{akitaya_et_al:LIPIcs.SoCG.2019.9, author = {Akitaya, Hugo A. and Korman, Matias and Rudoy, Mikhail and Souvaine, Diane L. and T\'{o}th, Csaba D.}, title = {{Circumscribing Polygons and Polygonizations for Disjoint Line Segments}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.9}, URN = {urn:nbn:de:0030-drops-104136}, doi = {10.4230/LIPIcs.SoCG.2019.9}, annote = {Keywords: circumscribing polygon, Hamiltonicity, extremal combinatorics} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, and Vincenzo Roselli. Morphing Contact Representations of Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{angelini_et_al:LIPIcs.SoCG.2019.10, author = {Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano and Roselli, Vincenzo}, title = {{Morphing Contact Representations of Graphs}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.10}, URN = {urn:nbn:de:0030-drops-104145}, doi = {10.4230/LIPIcs.SoCG.2019.10}, annote = {Keywords: Contact representations, Triangulations, Planar morphs, Schnyder woods} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Dominique Attali, André Lieutier, and David Salinas. When Convexity Helps Collapsing Complexes. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{attali_et_al:LIPIcs.SoCG.2019.11, author = {Attali, Dominique and Lieutier, Andr\'{e} and Salinas, David}, title = {{When Convexity Helps Collapsing Complexes}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {11:1--11:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.11}, URN = {urn:nbn:de:0030-drops-104152}, doi = {10.4230/LIPIcs.SoCG.2019.11}, annote = {Keywords: collapsibility, convexity, collection of compact convex sets, nerve, filtration, Delaunay complex, Cech complex, Rips complex} }
Feedback for Dagstuhl Publishing