International Symposium on Computational Geometry, SoCG 2017


Title/Authors Title Research Artifacts
[?] A research artifact is any by-product of a research project that is not directly included in the published research paper. In Computer Science research this is often source code and data sets, but it could also be media, documentation, inputs to proof assistants, shell-scripts to run experiments, etc.
Details

Barcodes of Towers and a Streaming Algorithm for Persistent Homology

Michael Kerber, Hannah Schreiber

Barcodes of Towers and a Streaming Algorithm for Persistent Homology

Details
Discussion Comments: 0
Verification: Authors have not verified information

Faster Algorithms for the Geometric Transportation Problem

Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, Allen Xiao

Faster Algorithms for the Geometric Transportation Problem

Details
Discussion Comments: 0
Verification: Authors have not verified information

High Dimensional Consistent Digital Segments

Man-Kwun Chiu, Matias Korman

High Dimensional Consistent Digital Segments

Details
Discussion Comments: 0
Verification: Authors have not verified information

Coloring Curves That Cross a Fixed Curve

Alexandre Rok, Bartosz Walczak

Coloring Curves That Cross a Fixed Curve

Details
Discussion Comments: 0
Verification: Authors have not verified information

Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves (Multimedia Contribution)

Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, Taichi Shiitada

Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves (Multimedia Contribution)

Details
Discussion Comments: 0
Verification: Authors have not verified information

An Approximation Algorithm for the Art Gallery Problem

Édouard Bonnet, Tillmann Miltzow

An Approximation Algorithm for the Art Gallery Problem

Details
Author Comments: It would be great if someone would actually implement the algorithm. Please let me know what your findings were.
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings

Lukas Barth, Benjamin Niedermann, Ignaz Rutter, Matthias Wolf

Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings

Details
Discussion Comments: 0
Verification: Authors have not verified information

Computing the Fréchet Gap Distance

Chenglin Fan, Benjamin Raichel

Computing the Fréchet Gap Distance

Details
Discussion Comments: 0
Verification: Authors have not verified information

Quickest Visibility Queries in Polygonal Domains

Haitao Wang

Quickest Visibility Queries in Polygonal Domains

Details
Discussion Comments: 0
Verification: Author has not verified information

Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane

Haitao Wang

Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane

Details
Discussion Comments: 0
Verification: Author has not verified information

Subquadratic Algorithms for Algebraic Generalizations of 3SUM

Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, Noam Solomon

Subquadratic Algorithms for Algebraic Generalizations of 3SUM

Details
Discussion Comments: 0
Verification: Authors have not verified information

Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension

Jacob Fox, János Pach, Andrew Suk

Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension

Details
Discussion Comments: 0
Verification: Authors have not verified information

Ham Sandwich is Equivalent to Borsuk-Ulam

Karthik C. S., Arpan Saha

Ham Sandwich is Equivalent to Borsuk-Ulam

Details
Discussion Comments: 0
Verification: Authors have not verified information

Lower Bounds for Differential Privacy from Gaussian Width

Assimakis Kattis, Aleksandar Nikolov

Lower Bounds for Differential Privacy from Gaussian Width

Details
Discussion Comments: 0
Verification: Authors have not verified information

MatchTheNet - An Educational Game on 3-Dimensional Polytopes (Multimedia Contribution)

Michael Joswig, Georg Loho, Benjamin Lorenz, Rico Raber

MatchTheNet - An Educational Game on 3-Dimensional Polytopes (Multimedia Contribution)

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Quest to Unravel the Metric Structure Behind Perturbed Networks

Srinivasan Parthasarathy, David Sivakoff, Minghao Tian, Yusu Wang

A Quest to Unravel the Metric Structure Behind Perturbed Networks

Details
Discussion Comments: 0
Verification: Authors have not verified information

Self-Approaching Paths in Simple Polygons

Prosenjit Bose, Irina Kostitsyna, Stefan Langerman

Self-Approaching Paths in Simple Polygons

Details
Discussion Comments: 0
Verification: Authors have not verified information

Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-Dimension

Khaled Elbassioni

Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-Dimension

Details
Discussion Comments: 0
Verification: Author has not verified information

Locality-Sensitive Hashing of Curves

Anne Driemel, Francesco Silvestri

Locality-Sensitive Hashing of Curves

Details
Discussion Comments: 0
Verification: Authors have not verified information

Local Equivalence and Intrinsic Metrics between Reeb Graphs

Mathieu Carrière, Steve Oudot

Local Equivalence and Intrinsic Metrics between Reeb Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs

Yi-Jun Chang, Hsu-Chun Yen

On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Best Laid Plans of Lions and Men

Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen

Best Laid Plans of Lions and Men

Details
Discussion Comments: 0
Verification: Authors have not verified information

Disjointness Graphs of Segments

János Pach, Gábor Tardos, Géza Tóth

Disjointness Graphs of Segments

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons

Eunjin Oh, Hee-Kap Ahn

Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Vanessa Robins

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

Details
Discussion Comments: 0
Verification: Author has not verified information

Range-Clustering Queries

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi

Range-Clustering Queries

Details
Discussion Comments: 0
Verification: Authors have not verified information

Algorithmic Interpretations of Fractal Dimension

Anastasios Sidiropoulos, Vijay Sridhar

Algorithmic Interpretations of Fractal Dimension

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Optimal 2- and 3-Planar Graphs

Michael A. Bekos, Michael Kaufmann, Chrysanthi N. Raftopoulou

On Optimal 2- and 3-Planar Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Maximum Volume Subset Selection for Anchored Boxes

Karl Bringmann, Sergio Cabello, Michael T. M. Emmerich

Maximum Volume Subset Selection for Anchored Boxes

Details
Discussion Comments: 0
Verification: Authors have not verified information

Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon

Eunjin Oh, Hee-Kap Ahn

Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon

Details
Discussion Comments: 0
Verification: Authors have not verified information

Exact Algorithms for Terrain Guarding

Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, Meirav Zehavi

Exact Algorithms for Terrain Guarding

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations

Anna Lubiw, Zuzana Masárová, Uli Wagner

A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations

Details
Discussion Comments: 0
Verification: Authors have not verified information

Computing the Geometric Intersection Number of Curves

Vincent Despré, Francis Lazarus

Computing the Geometric Intersection Number of Curves

Details
Discussion Comments: 0
Verification: Authors have not verified information

TSP With Locational Uncertainty: The Adversarial Model

Gui Citovsky, Tyler Mayer, Joseph S. B. Mitchell

TSP With Locational Uncertainty: The Adversarial Model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Ruler of the Plane - Games of Geometry (Multimedia Contribution)

Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, Willem Sonke

Ruler of the Plane - Games of Geometry (Multimedia Contribution)

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced artifacts
Verification: Authors have verified information

Fine-Grained Complexity of Coloring Unit Disks and Balls

Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Pawel Rzazewski

Fine-Grained Complexity of Coloring Unit Disks and Balls

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution)

Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, An Nguyen

Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution)

Details
Discussion Comments: 0
Verification: Authors have not verified information

Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning

Kunal Dutta, Arijit Ghosh, Bruno Jartoux, Nabil H. Mustafa

Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning

Details
Discussion Comments: 0
Verification: Authors have not verified information

Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams

Jean-Daniel Boissonnat, Mael Rouxel-Labbé, Mathijs Wintraecken

Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams

Details
Discussion Comments: 0
Verification: Authors have not verified information

Near-Optimal epsilon-Kernel Construction and Related Problems

Sunil Arya, Guilherme Dias da Fonseca, David M. Mount

Near-Optimal epsilon-Kernel Construction and Related Problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Declutter and Resample: Towards Parameter Free Denoising

Mickaël Buchet, Tamal K. Dey, Jiayuan Wang, Yusu Wang

Declutter and Resample: Towards Parameter Free Denoising

Details
Discussion Comments: 0
Verification: Authors have not verified information

Adaptive Planar Point Location

Siu-Wing Cheng, Man-Kit Lau

Adaptive Planar Point Location

Details
Discussion Comments: 0
Verification: Authors have not verified information

Reachability in a Planar Subdivision with Direction Constraints

Daniel Binham, Pedro Machado Manhaes de Castro, Antoine Vigneron

Reachability in a Planar Subdivision with Direction Constraints

Details
Discussion Comments: 0
Verification: Authors have not verified information

Cardiac Trabeculae Segmentation: an Application of Computational Topology (Multimedia Contribution)

Chao Chen, Dimitris N. Metaxas, Yusu Wang, Pengxiang Wu

Cardiac Trabeculae Segmentation: an Application of Computational Topology (Multimedia Contribution)

Details
Discussion Comments: 0
Verification: Authors have not verified information

Irrational Guards are Sometimes Needed

Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow

Irrational Guards are Sometimes Needed

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

On Balls in a Hilbert Polygonal Geometry (Multimedia Contribution)

Frank Nielsen, Laetitia Shao

On Balls in a Hilbert Polygonal Geometry (Multimedia Contribution)

Details
Discussion Comments: 0
Verification: Authors have not verified information

Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry

Timothy M. Chan

Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry

Details
Discussion Comments: 0
Verification: Author has not verified information

Approximate Range Counting Revisited

Saladi Rahul

Approximate Range Counting Revisited

Details
Discussion Comments: 0
Verification: Author has not verified information

A Spectral Gap Precludes Low-Dimensional Embeddings

Assaf Naor

A Spectral Gap Precludes Low-Dimensional Embeddings

Details
Discussion Comments: 0
Verification: Author has not verified information

Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back

Timothy M. Chan

Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back

Details
Discussion Comments: 0
Verification: Author has not verified information

A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM

Esther Ezra, Micha Sharir

A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Planar Greedy Drawings of 3-Connected Planar Graphs

Giordano Da Lozzo, Anthony D'Angelo, Fabrizio Frati

On Planar Greedy Drawings of 3-Connected Planar Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Superlinear Lower Bound on the Number of 5-Holes

Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber

A Superlinear Lower Bound on the Number of 5-Holes

Details
Discussion Comments: 0
Verification: Authors have not verified information

Computing Representative Networks for Braided Rivers

Maarten Kleinhans, Marc J. van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, Kevin Verbeek

Computing Representative Networks for Braided Rivers

Details
Discussion Comments: 0
Verification: Authors have not verified information

Origamizer: A Practical Algorithm for Folding Any Polyhedron

Erik D. Demaine, Tomohiro Tachi

Origamizer: A Practical Algorithm for Folding Any Polyhedron

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Number of Ordinary Lines Determined by Sets in Complex Space

Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf

On the Number of Ordinary Lines Determined by Sets in Complex Space

Details
Discussion Comments: 0
Verification: Authors have not verified information

From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices

Alexander Pilz, Emo Welzl, Manuel Wettstein

From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices

Details
Discussion Comments: 0
Verification: Authors have not verified information

Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers

Tamal K. Dey, Facundo Mémoli, Yusu Wang

Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers

Details
Discussion Comments: 0
Verification: Authors have not verified information

Constrained Triangulations, Volumes of Polytopes, and Unit Equations

Michael Kerber, Robert Tichy, Mario Weitzer

Constrained Triangulations, Volumes of Polytopes, and Unit Equations

Details
Discussion Comments: 0
Verification: Authors have not verified information

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

Micha Sharir

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

Details
Discussion Comments: 0
Verification: Author has not verified information

Topological Data Analysis with Bregman Divergences

Herbert Edelsbrunner, Hubert Wagner

Topological Data Analysis with Bregman Divergences

Details
Discussion Comments: 0
Verification: Authors have not verified information

Implementing Delaunay Triangulations of the Bolza Surface

Iordan Iordanov, Monique Teillaud

Implementing Delaunay Triangulations of the Bolza Surface

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Universal Slope Set for 1-Bend Planar Drawings

Patrizio Angelini, Michael A. Bekos, Giuseppe Liotta, Fabrizio Montecchiani

A Universal Slope Set for 1-Bend Planar Drawings

Details
Discussion Comments: 0
Verification: Authors have not verified information

Minimum Perimeter-Sum Partitions in the Plane

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi

Minimum Perimeter-Sum Partitions in the Plane

Details
Discussion Comments: 0
Verification: Authors have not verified information

Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences

Martin Balko, Josef Cibulka, Pavel Valtr

Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences

Details
Discussion Comments: 0
Verification: Authors have not verified information

Proper Coloring of Geometric Hypergraphs

Balázs Keszegh, Dömötör Pálvölgyi

Proper Coloring of Geometric Hypergraphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dynamic Orthogonal Range Searching on the RAM, Revisited

Timothy M. Chan, Konstantinos Tsakalidis

Dynamic Orthogonal Range Searching on the RAM, Revisited

Details
Discussion Comments: 0
Verification: Authors have not verified information