Portal - SoCG 2017

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

Boissonnat, Jean-Daniel

da Fonseca, Guilherme D.

Edelsbrunner, Herbert

Elbassioni, Khaled

Emmerich, Michael T. M.

Manhaes de Castro, Pedro Machado

Mitchell, Joseph S. B.

Montecchiani, Fabrizio

Parthasarathy, Srinivasan

Pilz, Alexander

Pálvölgyi, Dömötör

Raber, Rico

Raftopoulou, Chrysanthi N.

Sidiropoulos, Anastasios

Tsakalidis, Konstantinos

Tóth, Géza

Valtr, Pavel

van Kreveld, Marc

Varadarajan, Kasturi R.

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 | Privacy Published by LZI

33rd International Symposium on Computational Geometry (SoCG 2017)