SoCG 2021

The 37th International Symposium on Computational Geometry

SoCG 2021 Accepted Papers

Sariel Har-Peled and Mitchell Jones. Stabbing Convex Bodies with Lines and Flats
Jean-Daniel Boissonnat, Siargey Kachanovich and Mathijs Wintraecken. Tracing isomanifolds in $\mathbb{R}^d$ in time polynomial in $d$ using Coxeter-Freudenthal-Kuhn triangulations
Haitao Wang. An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons
Esther Ezra and Micha Sharir. On Ray Shooting for Triangles in 3-Space and Related Problems
Ziyue Huang and Ke Yi. Approximate Range Counting under Differential Privacy
Sándor Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist and Christian Scheffer. Packing Squares into a Disk with Optimal Worst-Case Density
Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee and Bodhayan Roy. Complexity of Maximum Cut on Interval Graphs
Denys Bulavka, Afshin Goodarzi and Martin Tancer. Optimal bounds for the colorful fractional Helly theorem
David Eppstein and Hadi Khodabandeh. On the Edge Crossings of the Greedy Spanner
Jacob Fox, Janos Pach and Andrew Suk. Sunflowers in set systems of bounded dimension
Erin Chambers, Elizabeth Munch and Tim Ophelders. A family of metrics from the truncated smoothing of Reeb graphs
Esther Ezra, Orit E. Raz, Micha Sharir and Joshua Zahl. On rich lenses in planar arrangements of circles and related problems
Dan Halperin, Micha Sharir and Itay Yehuda. Throwing a sofa through the window
Goran Malic and Ileana Streinu. Combinatorial Resultants in the Algebraic Rigidity Matroid
Arturo Merino and Torsten Mütze. Efficient generation of rectangulations via permutation languages
Sariel Har-Peled, Manor Mendel and Dániel Oláh. Reliable Spanners for Metric Spaces
Aditi Laddha and Santosh Vempala. Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast
Stav Ashur and Sariel Har-Peled. On Undecided LP and Active Learning Using Proximity Queries
Herbert Edelsbrunner, Teresa Heiss, Vitaliy Kurlin, Philip Smith and Mathijs Wintraecken. The Density Fingerprint of a Periodic Point Set
Radoslav Fulek, Marcus Schaefer and Michael Pelsmajer. Strong Hanani-Tutte for the Torus
Chaya Keller and Micha A. Perles. No Krasnoselskii Number for General Sets
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Till Miltzow, Jérôme Urhausen, Jordi Vermeulen and Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves
Simon Hengeveld and Till Miltzow. A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen and Peter M. R. Rasmussen. Classifying Convex Bodies by their Contact and Intersection Graphs
Henk Alkema and Mark de Berg. Rectilinear Steiner Trees in Narrow Strips
Mikkel Abrahamsen and Lorenzo Beretta. Online Packing to Minimize Area or Perimeter
Peyman Afshani and Pingan Cheng. Lower Bounds for Semialgebraic Range Searching and Stabbing Problems (Best Paper Award)
Clément Maria. Parameterized Complexity of Quantum Knot Invariants
Deepanshu Kush, Aleksandar Nikolov and Haohua Tang. Near Neighbour Search via Efficient Average Distortion Embeddings
Monika Csikos and Nabil H. Mustafa. Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and their Applications
Sujoy Bhore and Csaba Toth. Light Euclidean Steiner Spanners in the Plane
Donald Sheehy and Siddharth Sheth. Sketching Persistence Diagrams
Don Sheehy. A Sparse Delaunay Filtration
Xavier Goaoc, Andreas Holmsen and Zuzana Patáková. A stepping-up lemma for topological set systems
René Corbet, Michael Kerber, Michael Lesnick and Georg Osang. Computing the multicover bifiltration
Yiqiu Wang, Shangdi Yu, Yan Gu and Julian Shun. An Experimental Study of a New Parallel Batch-Dynamic Closest Pair Data Structure
Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero and Andreas Wiese. Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
Marc Khoury and Jonathan Shewchuk. Restricted Constrained Delaunay Triangulations
Micha Sharir and Noam Solomon. On rich points and incidences with restricted sets of lines in 3-space
Hadrien Cambazard and Nicolas Catusse. An integer programming formulation using convex polygons for the convex partition problem
Tim Ophelders, Ignaz Rutter, Bettina Speckmann and Kevin Verbeek. Polygon-Universal Graphs
Ranita Biswas, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner and Morteza Saghafian. Counting Cells of Order-k Voronoi Tessellations in R^3 with Morse Theory
Matthijs Ebbens, Hugo Parlier and Gert Vegter. Minimal Delaunay triangulations of hyperbolic surfaces
Erin Chambers, Francis Lazarus, Arnaud De Mesmay and Salman Parsa. Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries
Imre Bárány, Attila Pór and Pavel Valtr. Orientation preserving Maps of the n × n Grid
Timothy M. Chan. Faster Algorithms for Largest Empty Rectangles and Boxes
Tamal K. Dey and Tao Hou. Computing Zigzag Persistence on Graphs in Near-Linear Time
Karl Bringmann and André Nusser. Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation
Connor Colombe and Kyle Fox. Approximating the (Continuous) Fréchet Distance
Adam Karczmarz, Jakub Pawlewicz and Piotr Sankowski. Sublinear average-case shortest paths in weighted unit-disk graphs
Ahmed Abdelkader and David Mount. Approximate Nearest-Neighbor Search for Line Segments
Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces
Timothy M. Chan and Qizheng He. More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time
Apostolos Chalkis, Vissarion Fisikopoulos, Elias Tsigaridas and Haris Zafeiropoulos. Geometric algorithms for sampling the flux space of metabolic networks
James Davies, Tomasz Krawczyk, Rose McCarty and Bartosz Walczak. Colouring polygon visibility graphs and their generalizations
Hugo Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korter, Jayson Lynch, Irene Parada and Vera Sacristán. Characterizing Universal Reconfigurability of Modular Pivoting Robots
Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev and Yury Makarychev. Two-sided Kirszbraun Theorem
Arindam Khan, Arnab Maiti, Amatya Sharma and Andreas Wiese. On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem