SoCG 2019: List of Accepted Papers

Adrian Dumitrescu. A Product Inequality for Extreme Distances
Sariel Har-Peled and Mitchell Jones. Journey to the Center of the Point Set
Xavier Goaoc, Andreas Holmsen and Cyril Nicaud. An experimental study of forbidden patterns in geometric permutations by combinatorial lifting
Shay Moran and Amir Yehudayoff. On weak ϵ-nets and the Radon number
Raphaël Tinarrage, Frederic Chazal, Marc Glisse, Hirokazu Anai, Yuichi Ike, Hiroya Inakoshi and Yuhei Umeda. DTM-based filtrations
Mozhgan Mirzaei and Andrew Suk. On grids in point-line arrangements in the plane
Janos Pach and Istvan Tomon. On the chromatic number of disjointness graphs of curves
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff and Lin F. Yang. The One-Way Communication Complexity of Dynamic Time Warping Distance
Diego Ihara, Neshat Mohammadi and Anastasios Sidiropoulos. Algorithms for metric learning via contrastive embeddings
Pankaj K. Agarwal, Boris Aronov, Esther Ezra and Joshua Zahl. An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Haitao Wang. A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains
Akanksha Agrawal, Grzegorz Guspiel, Jayakrishnan Madathil, Saket Saurabh and Meirav Zehavi. Connecting the Dots (with Minimum Crossings)
Sándor Fekete, Phillip Keldenich and Christian Scheffer. Packing Disks into Disks with Optimal Worst-Case Density
Dominique Attali, Andre Lieutier and David Salinas. When convexity helps collapsing complexes
Luis Barba. Optimal algorithm for geodesic farthest-point Voronoi diagrams
Vida Dujmovic and Pat Morin. Dual Circumference and Collinear Sets
Timothy M. Chan and Sariel Har-Peled. Smallest k-Enclosing Rectangle Revisited
Chen Ziv and Micha Sharir. On the Complexity of the k-Level in Arrangements of Pseudoplanes
Yufei Tao and Yu Wang. Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges
Sergio Cabello and Timothy M. Chan. Computing Shapley values in the plane
Jean-Lou de Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth and Sander Verdonschot. Convex Polygons in Cartesian Products
Dror Aiger, Haim Kaplan, Efi Kokiopoulou, Micha Sharir and Bernhard Zeisl. General techniques for approximate incidences and their application to the camera posing problem
Arnaud de Mesmay, Yo'Av Rieck, Martin Tancer and Eric Sedgwick. The Unbearable Hardness of Unknotting
Jacob Fox, Janos Pach and Andrew Suk. Semi-algebraic colorings of complete graphs
Kevin Buchin, Sariel Har-Peled and Dániel Oláh. A Spanner for the Day After
Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx and Arnaud de Mesmay. Almost tight lower bounds for hard cutting problems in embedded graphs
Drago Bokal, Zdenek Dvorak, Petr Hlineny, Jesus Leanos, Bojan Mohar and Tilo Wiedera. Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12
Karl Bringmann, Marvin Künnemann and André Nusser. Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
Karl Bringmann and Bhaskar Ray Chaudhury. Polyline Simplification has Cubic Complexity
Anne Driemel, Jeff Phillips and Ioannis Psarros. On the VC dimension of metric balls under Fr'echet and Hausdorff distances
Ching-Hsiang Hsu, Yi-Jen Chiang and Chee Yap. Rods and Rings: Soft Subdivision Planner for R^3 x S^2
David Eppstein. Cubic Planar Graphs That Cannot Be Drawn On Few Lines
David Eppstein. Counting Polygon Triangulations is Hard
Haitao Wang and Jie Xue. Near-optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs
Andrey Boris Khesin, Aleksandar Nikolov and Dmitry Paramonov. Preconditioning for the Geometric Transportation Problem
Timothy M. Chan. Dynamic Geometric Data Structures via Shallow Cuttings
Radoslav Fulek and Jan Kynčl. Z_2-genus of graphs and minimum rank of partial symmetric matrices
Jie Xue, Yuan Li, Saladi Rahul and Ravi Janardan. Searching for the closest-pair in a query translate
Benjamin Niedermann, Ignaz Rutter and Matthias Wolf. Efficient Algorithms for Ortho-Radial Graph Drawing
Pankaj K. Agarwal, Hsien-Chih Chang and Allen Xiao. Geometric Partial Matching and Unbalanced Transportation
Kristóf Huszár and Jonathan Spreer. 3-Manifold triangulations of small treewidth
Patrick Schnider. Ham-Sandwich cuts and center transversals in subspaces
Amer Krivosija and Alexander Munteanu. Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
Michael Kerber, Michael Lesnick and Steve Oudot. Exact computation of the matching distance on 2-parameter persistence modules
Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr and Uli Wagner. The Crossing Tverberg Theorem
Siddharth Pritam and Jean-Daniel Boissonnat. Computing Persistent Homology of Flag Complexes via Strong Collapses
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo and Vincenzo Roselli. Morphing Contact Representations of Graphs
Ravid Cohen, Dan Halperin, Pankaj K. Agarwal and Wolfgang Mulzer. Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead
Hsien-Chih Chang, Marcos Cossarini and Jeff Erickson. Lower Bounds for Electrical Reduction on Surfaces
Peyman Afshani. A New Lower Bound for Semigroup Orthogonal Range Searching
Jeff Erickson and Yipu Wang. Topologically Trivial Closed Walks in Directed Surface Graphs
Peyman Afshani and Jeff Phillips. Independent Range Sampling, Revisited Again
Ulderico Fugacci and Michael Kerber. Chunk Reduction for Multi-Parameter Persistent Homology
Nathaniel Lahn and Sharath Raghvendra. A Weighted Approach to Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
Ian Munro and Yakov Nekrich. Dynamic Planar Point Location in External Memory
Herbert Edelsbrunner, Žiga Virk and Hubert Wagner. Topological Data Analysis in Information Space
Hugo Akitaya, Matias Korman, Mikhail Rudoy, Diane Souvaine and Csaba Toth. Circumscribing Polygons and Polygonizations for Disjoint Line Segments
Ivor Hoog V.D., Irina Kostitsyna, Bettina Speckmann and Maarten Löffler. Preprocessing Ambiguous Imprecise Points
Mathieu Carrière and Ulrich Bauer. On the Metric Distortion of Embedding Persistence Diagrams into separable Hilbert spaces