SoCG 2017 July 4-7, 2017 - Brisbane, Australia

33rd International Symposium on Computational Geometry (SoCG 2017)



Boris Aronov and Matthew J. Katz (Eds.)
ISBN 978-3-95977-038-5, LIPICS Vol. 77 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 58 MB)
Search Publication Server


Authors
  • Abrahamsen, Mikkel
  • Adamaszek, Anna
  • Agarwal, Pankaj K.
  • Ahn, Hee-Kap
  • Aichholzer, Oswin
  • Angelini, Patrizio
  • Aronov, Boris
  • Arya, Sunil
  • Ashok, Pradeesha
  • Balko, Martin
  • Barba, Luis
  • Barth, Lukas
  • Basit, Abdul
  • Becker, Aaron T.
  • Beekhuis, Sander
  • Bekos, Michael A.
  • Binham, Daniel
  • Biró, Csaba
  • Boissonnat, Jean-Daniel
  • Bonnet, Édouard
  • Bose, Prosenjit
  • Bringmann, Karl
  • Buchet, Mickael
  • Buchin, Kevin
  • C. S., Karthik
  • Cabello, Sergio
  • Cardinal, Jean
  • Carričre, Mathieu
  • Castermans, Thom
  • Chan, Timothy M.
  • Chang, Yi-Jun
  • Chen, Chao
  • Cheng, Siu-Wing
  • Chiu, Man-Kwun
  • Chun, Jinhee
  • Cibulka, Josef
  • Citovsky, Gui
  • D'Angelo, Anthony
  • da Fonseca, Guilherme D.
  • Da Lozzo, Giordano
  • Debboun, Mustapha
  • de Berg, Mark
  • Demaine, Erik D.
  • Despré, Vincent
  • Dey, Tamal K.
  • Driemel, Anne
  • Dutta, Kunal
  • Dvir, Zeev
  • Edelsbrunner, Herbert
  • Elbassioni, Khaled
  • Emmerich, Michael T. M.
  • Ezra, Esther
  • Fan, Chenglin
  • Fekete, Sándor P.
  • Fomin, Fedor V.
  • Fox, Jacob
  • Fox, Kyle
  • Frati, Fabrizio
  • Ghosh, Arijit
  • Hackl, Thomas
  • Holm, Jacob
  • Hurks, Thom
  • Iacono, John
  • Iordanov, Iordan
  • Jartoux, Bruno
  • Joswig, Michael
  • Kattis, Assimakis
  • Katz, Matthew J.
  • Kaufmann, Michael
  • Kerber, Michael
  • Keszegh, Balázs
  • Kleinhans, Maarten
  • Kolay, Sudeshna
  • Korman, Matias
  • Kostitsyna, Irina
  • Krupke, Dominik
  • Kyncl, Jan
  • Löffler, Maarten
  • Langerman, Stefan
  • Lau, Man-Kit
  • Lazarus, Francis
  • Liotta, Giuseppe
  • Loho, Georg
  • Lorenz, Benjamin
  • Lubiw, Anna
  • Mémoli, Facundo
  • Manhaes de Castro, Pedro Machado
  • Markovic, Aleksandar
  • Marx, Dániel
  • Masárová, Zuzana
  • Mayer, Tyler
  • Mehr, Mehran
  • Mehrabi, Ali D.
  • Metaxas, Dimitris
  • Meulemans, Wouter
  • Miltzow, Tillmann
  • Mitchell, Joseph S. B.
  • Montecchiani, Fabrizio
  • Mount, David M.
  • Mustafa, Nabil H.
  • Naor, Assaf
  • Nguyen, An
  • Niedermann, Benjamin
  • Nielsen, Frank
  • Nikolov, Aleksandar
  • Oh, Eunjin
  • Okamoto, Yoshio
  • Ooms, Aurélien
  • Ophelders, Tim
  • Oudot, Steve
  • Pálvölgyi, Dömötör
  • Pach, János
  • Panigrahi, Debmalya
  • Parada, Irene
  • Parthasarathy, Srinivasan
  • Pilz, Alexander
  • Raber, Rico
  • Raftopoulou, Chrysanthi N.
  • Rahul, Saladi
  • Raichel, Benjamin
  • Robins, Vanessa
  • Rok, Alexandre
  • Rotenberg, Eva
  • Rouxel-Labbé, Mael
  • Rutter, Ignaz
  • Rzazewski, Pawel
  • Saha, Arpan
  • Saraf, Shubhangi
  • Saurabh, Saket
  • Scheucher, Manfred
  • Schreiber, Hannah
  • Shao, Laetitia
  • Sharir, Micha
  • Shiitada, Taichi
  • Sidiropoulos, Anastasios
  • Silvestri, Francesco
  • Sivakoff, David
  • Solomon, Noam
  • Sonke, Willem
  • Speckmann, Bettina
  • Sridhar, Vijay
  • Suk, Andrew
  • Tóth, Géza
  • Tachi, Tomohiro
  • Tardos, Gábor
  • Teillaud, Monique
  • Tian, Minghao
  • Tichy, Robert
  • Tsakalidis, Konstantinos
  • Valtr, Pavel
  • van Kreveld, Marc
  • Varadarajan, Kasturi R.
  • Verbeek, Kevin
  • Vigneron, Antoine
  • Vogtenhuber, Birgit
  • Wagner, Hubert
  • Wagner, Uli
  • Walczak, Bartosz
  • Wang, Haitao
  • Wang, Jiayuan
  • Wang, Yusu
  • Weitzer, Mario
  • Welzl, Emo
  • Wettstein, Manuel
  • Wintraecken, Mathijs
  • Wolf, Charles
  • Wolf, Matthias
  • Wu, Pengxiang
  • Wulff-Nilsen, Christian
  • Xiao, Allen
  • Yen, Hsu-Chun
  • Zehavi, Meirav

  •   
    Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors
    Authors: Aronov, Boris ; Katz, Matthew J.

    Abstract | Document (368 KB) | BibTeX

    The Geometry and Topology of Crystals: From Sphere-Packing to Tiling, Nets, and Knots (Invited Talk)
    Authors: Robins, Vanessa

    Abstract | Document (235 KB) | BibTeX

    The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art (Invited Talk)
    Authors: Sharir, Micha

    Abstract | Document (201 KB) | BibTeX

    Irrational Guards are Sometimes Needed
    Authors: Abrahamsen, Mikkel ; Adamaszek, Anna ; Miltzow, Tillmann

    Abstract | Document (2,697 KB) | BibTeX

    Minimum Perimeter-Sum Partitions in the Plane
    Authors: Abrahamsen, Mikkel ; de Berg, Mark ; Buchin, Kevin ; Mehr, Mehran ; Mehrabi, Ali D.

    Abstract | Document (652 KB) | BibTeX

    Range-Clustering Queries
    Authors: Abrahamsen, Mikkel ; de Berg, Mark ; Buchin, Kevin ; Mehr, Mehran ; Mehrabi, Ali D.

    Abstract | Document (621 KB) | BibTeX

    Best Laid Plans of Lions and Men
    Authors: Abrahamsen, Mikkel ; Holm, Jacob ; Rotenberg, Eva ; Wulff-Nilsen, Christian

    Abstract | Document (616 KB) | BibTeX

    Faster Algorithms for the Geometric Transportation Problem
    Authors: Agarwal, Pankaj K. ; Fox, Kyle ; Panigrahi, Debmalya ; Varadarajan, Kasturi R. ; Xiao, Allen

    Abstract | Document (707 KB) | BibTeX

    A Superlinear Lower Bound on the Number of 5-Holes
    Authors: Aichholzer, Oswin ; Balko, Martin ; Hackl, Thomas ; Kyncl, Jan ; Parada, Irene ; Scheucher, Manfred ; Valtr, Pavel ; Vogtenhuber, Birgit

    Abstract | Document (592 KB) | BibTeX

    A Universal Slope Set for 1-Bend Planar Drawings
    Authors: Angelini, Patrizio ; Bekos, Michael A. ; Liotta, Giuseppe ; Montecchiani, Fabrizio

    Abstract | Document (936 KB) | BibTeX

    Near-Optimal epsilon-Kernel Construction and Related Problems
    Authors: Arya, Sunil ; da Fonseca, Guilherme D. ; Mount, David M.

    Abstract | Document (583 KB) | BibTeX

    Exact Algorithms for Terrain Guarding
    Authors: Ashok, Pradeesha ; Fomin, Fedor V. ; Kolay, Sudeshna ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (859 KB) | BibTeX

    Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences
    Authors: Balko, Martin ; Cibulka, Josef ; Valtr, Pavel

    Abstract | Document (543 KB) | BibTeX

    Subquadratic Algorithms for Algebraic Generalizations of 3SUM
    Authors: Barba, Luis ; Cardinal, Jean ; Iacono, John ; Langerman, Stefan ; Ooms, Aurélien ; Solomon, Noam

    Abstract | Document (1,049 KB) | BibTeX

    Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings
    Authors: Barth, Lukas ; Niedermann, Benjamin ; Rutter, Ignaz ; Wolf, Matthias

    Abstract | Document (1,685 KB) | BibTeX

    On the Number of Ordinary Lines Determined by Sets in Complex Space
    Authors: Basit, Abdul ; Dvir, Zeev ; Saraf, Shubhangi ; Wolf, Charles

    Abstract | Document (530 KB) | BibTeX

    On Optimal 2- and 3-Planar Graphs
    Authors: Bekos, Michael A. ; Kaufmann, Michael ; Raftopoulou, Chrysanthi N.

    Abstract | Document (1,025 KB) | BibTeX

    Reachability in a Planar Subdivision with Direction Constraints
    Authors: Binham, Daniel ; Manhaes de Castro, Pedro Machado ; Vigneron, Antoine

    Abstract | Document (632 KB) | BibTeX

    Fine-Grained Complexity of Coloring Unit Disks and Balls
    Authors: Biró, Csaba ; Bonnet, Édouard ; Marx, Dániel ; Miltzow, Tillmann ; Rzazewski, Pawel

    Abstract | Document (815 KB) | BibTeX

    Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams
    Authors: Boissonnat, Jean-Daniel ; Rouxel-Labbé, Mael ; Wintraecken, Mathijs

    Abstract | Document (1,732 KB) | BibTeX

    An Approximation Algorithm for the Art Gallery Problem
    Authors: Bonnet, Édouard ; Miltzow, Tillmann

    Abstract | Document (909 KB) | BibTeX

    Self-Approaching Paths in Simple Polygons
    Authors: Bose, Prosenjit ; Kostitsyna, Irina ; Langerman, Stefan

    Abstract | Document (816 KB) | BibTeX

    Maximum Volume Subset Selection for Anchored Boxes
    Authors: Bringmann, Karl ; Cabello, Sergio ; Emmerich, Michael T. M.

    Abstract | Document (661 KB) | BibTeX

    Declutter and Resample: Towards Parameter Free Denoising
    Authors: Buchet, Mickael ; Dey, Tamal K. ; Wang, Jiayuan ; Wang, Yusu

    Abstract | Document (1,207 KB) | BibTeX

    Ham Sandwich is Equivalent to Borsuk-Ulam
    Authors: C. S., Karthik ; Saha, Arpan

    Abstract | Document (553 KB) | BibTeX

    Local Equivalence and Intrinsic Metrics between Reeb Graphs
    Authors: Carričre, Mathieu ; Oudot, Steve

    Abstract | Document (638 KB) | BibTeX

    Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry
    Authors: Chan, Timothy M.

    Abstract | Document (513 KB) | BibTeX

    Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back
    Authors: Chan, Timothy M.

    Abstract | Document (550 KB) | BibTeX

    Dynamic Orthogonal Range Searching on the RAM, Revisited
    Authors: Chan, Timothy M. ; Tsakalidis, Konstantinos

    Abstract | Document (487 KB) | BibTeX

    On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs
    Authors: Chang, Yi-Jun ; Yen, Hsu-Chun

    Abstract | Document (2,005 KB) | BibTeX

    Adaptive Planar Point Location
    Authors: Cheng, Siu-Wing ; Lau, Man-Kit

    Abstract | Document (545 KB) | BibTeX

    High Dimensional Consistent Digital Segments
    Authors: Chiu, Man-Kwun ; Korman, Matias

    Abstract | Document (740 KB) | BibTeX

    TSP With Locational Uncertainty: The Adversarial Model
    Authors: Citovsky, Gui ; Mayer, Tyler ; Mitchell, Joseph S. B.

    Abstract | Document (651 KB) | BibTeX

    On Planar Greedy Drawings of 3-Connected Planar Graphs
    Authors: Da Lozzo, Giordano ; D'Angelo, Anthony ; Frati, Fabrizio

    Abstract | Document (1,027 KB) | BibTeX

    Origamizer: A Practical Algorithm for Folding Any Polyhedron
    Authors: Demaine, Erik D. ; Tachi, Tomohiro

    Abstract | Document (8,228 KB) | BibTeX

    Computing the Geometric Intersection Number of Curves
    Authors: Despré, Vincent ; Lazarus, Francis

    Abstract | Document (662 KB) | BibTeX

    Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers
    Authors: Dey, Tamal K. ; Mémoli, Facundo ; Wang, Yusu

    Abstract | Document (1,318 KB) | BibTeX

    Locality-Sensitive Hashing of Curves
    Authors: Driemel, Anne ; Silvestri, Francesco

    Abstract | Document (566 KB) | BibTeX

    Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning
    Authors: Dutta, Kunal ; Ghosh, Arijit ; Jartoux, Bruno ; Mustafa, Nabil H.

    Abstract | Document (664 KB) | BibTeX

    Topological Data Analysis with Bregman Divergences
    Authors: Edelsbrunner, Herbert ; Wagner, Hubert

    Abstract | Document (967 KB) | BibTeX

    Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-Dimension
    Authors: Elbassioni, Khaled

    Abstract | Document (604 KB) | BibTeX

    A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM
    Authors: Ezra, Esther ; Sharir, Micha

    Abstract | Document (540 KB) | BibTeX

    Computing the Fréchet Gap Distance
    Authors: Fan, Chenglin ; Raichel, Benjamin

    Abstract | Document (698 KB) | BibTeX

    Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension
    Authors: Fox, Jacob ; Pach, János ; Suk, Andrew

    Abstract | Document (506 KB) | BibTeX

    Implementing Delaunay Triangulations of the Bolza Surface
    Authors: Iordanov, Iordan ; Teillaud, Monique

    Abstract | Document (1,244 KB) | BibTeX

    Lower Bounds for Differential Privacy from Gaussian Width
    Authors: Kattis, Assimakis ; Nikolov, Aleksandar

    Abstract | Document (517 KB) | BibTeX

    Constrained Triangulations, Volumes of Polytopes, and Unit Equations
    Authors: Kerber, Michael ; Tichy, Robert ; Weitzer, Mario

    Abstract | Document (1,173 KB) | BibTeX

    Proper Coloring of Geometric Hypergraphs
    Authors: Keszegh, Balázs ; Pálvölgyi, Dömötör

    Abstract | Document (863 KB) | BibTeX

    Computing Representative Networks for Braided Rivers
    Authors: Kleinhans, Maarten ; van Kreveld, Marc ; Ophelders, Tim ; Sonke, Willem ; Speckmann, Bettina ; Verbeek, Kevin

    Abstract | Document (5,288 KB) | BibTeX

    A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations
    Authors: Lubiw, Anna ; Masárová, Zuzana ; Wagner, Uli

    Abstract | Document (693 KB) | BibTeX

    A Spectral Gap Precludes Low-Dimensional Embeddings
    Authors: Naor, Assaf

    Abstract | Document (491 KB) | BibTeX

    Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons
    Authors: Oh, Eunjin ; Ahn, Hee-Kap

    Abstract | Document (591 KB) | BibTeX

    Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon
    Authors: Oh, Eunjin ; Ahn, Hee-Kap

    Abstract | Document (632 KB) | BibTeX

    A Quest to Unravel the Metric Structure Behind Perturbed Networks
    Authors: Parthasarathy, Srinivasan ; Sivakoff, David ; Tian, Minghao ; Wang, Yusu

    Abstract | Document (735 KB) | BibTeX

    From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices
    Authors: Pilz, Alexander ; Welzl, Emo ; Wettstein, Manuel

    Abstract | Document (629 KB) | BibTeX

    Approximate Range Counting Revisited
    Authors: Rahul, Saladi

    Abstract | Document (658 KB) | BibTeX

    Coloring Curves That Cross a Fixed Curve
    Authors: Rok, Alexandre ; Walczak, Bartosz

    Abstract | Document (512 KB) | BibTeX

    Barcodes of Towers and a Streaming Algorithm for Persistent Homology
    Authors: Kerber, Michael ; Schreiber, Hannah

    Abstract | Document (640 KB) | BibTeX

    Algorithmic Interpretations of Fractal Dimension
    Authors: Sidiropoulos, Anastasios ; Sridhar, Vijay

    Abstract | Document (621 KB) | BibTeX

    Disjointness Graphs of Segments
    Authors: Pach, János ; Tardos, Gábor ; Tóth, Géza

    Abstract | Document (443 KB) | BibTeX

    Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane
    Authors: Wang, Haitao

    Abstract | Document (594 KB) | BibTeX

    Quickest Visibility Queries in Polygonal Domains
    Authors: Wang, Haitao

    Abstract | Document (580 KB) | BibTeX

    Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution)
    Authors: Becker, Aaron T. ; Debboun, Mustapha ; Fekete, Sándor P. ; Krupke, Dominik ; Nguyen, An

    Abstract | Document (1,441 KB) | BibTeX

    Ruler of the Plane - Games of Geometry (Multimedia Contribution)
    Authors: Beekhuis, Sander ; Buchin, Kevin ; Castermans, Thom ; Hurks, Thom ; Sonke, Willem

    Abstract | Document (2,333 KB) | BibTeX

    Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves (Multimedia Contribution)
    Authors: Buchin, Kevin ; Chun, Jinhee ; Löffler, Maarten ; Markovic, Aleksandar ; Meulemans, Wouter ; Okamoto, Yoshio ; Shiitada, Taichi

    Abstract | Document (411 KB) | BibTeX

    Cardiac Trabeculae Segmentation: an Application of Computational Topology (Multimedia Contribution)
    Authors: Chen, Chao ; Metaxas, Dimitris ; Wang, Yusu ; Wu, Pengxiang

    Abstract | Document (1,990 KB) | BibTeX

    MatchTheNet - An Educational Game on 3-Dimensional Polytopes (Multimedia Contribution)
    Authors: Joswig, Michael ; Loho, Georg ; Lorenz, Benjamin ; Raber, Rico

    Abstract | Document (493 KB) | BibTeX

    On Balls in a Hilbert Polygonal Geometry (Multimedia Contribution)
    Authors: Nielsen, Frank ; Shao, Laetitia

    Abstract | Document (673 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI