The SoCG-logo for 2022

SoCG 2022

7–10 June 2022 in Berlin, Germany

The SoCG-logo
Call for Papers: 38th SoCG – June 7–10, 2022

The 38th International Symposium on Computational Geometry (SoCG 2022) is planned to be held in Berlin, Germany, June 7–10, 2022, as part of the Computational Geometry (CG) Week. We invite submissions of high quality that describe original research on computational problems in a geometric setting. Topics of interest include, but are not limited to:

Important Dates
Conference Web Page

Program Committee
Submit via the EasyChair Link

Submission Guidelines
Accepted Papers
Code of Conduct

SoCG is dedicated to providing an environment that is free from harassment, bullying, discrimination, and retaliation for all participants. All attendees, speakers, sponsors, and volunteers at our conference are required to agree with the CG Week code of conduct.

If an author has a conflict of such nature with a potential reviewer, and the author has sufficient grounds to believe that the review would be negatively biased, then the author is asked to declare this conflict by contacting a SoCG advocate who will treat any supporting information confidentially. For a list of SoCG advocates with contact information, please refer to

List of Accepted Papers
Authors Title
Robert Cardona, Justin Curry, Tung Lam and Michael Lesnick The Universal ℓp-Metric on Merge Trees
Shir Peleg and Amir Shpilka Robust Sylvester-Gallai type theorem for quadratic polynomials
Rafael Mendes de Oliveira, Akash Sengupta and Abhibhav Garg Robust Radical Sylvester-Gallai Theorem for Quadratics
Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang and Hao-Tsung Yang On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem
Rajesh Chitnis and Nitin Saurabh Tight Lower Bounds for Approximate & Exact k-Center in ℝd
Zdenek Dvorak, Jakub Pekarek, Torsten Ueckerdt and Yelena Yuditsky Weak Coloring Numbers of Intersection Graphs
Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts and Galyna Livshyts Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky and Bartosz Walczak A solution to Ringel's circle problem
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser and Zahra Parsaeian Towards sub-quadratic diameter computation in geometric intersection graphs
Everett Yang and Sariel Har-Peled Approximation Algorithms for Maximum Matching in Disk Intersection Graphs
Sergio Cabello, Michael Hoffmann, Katharina Klost, Wolfgang Mulzer and Josef Tkadlec Long plane trees
Andrew Suk and Ji Zeng A positive fraction Erdős-Szekeres theorem and its applications
Håvard Bakke Bjerkevik Tighter bounds for reconstruction from ε-samples
Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri and Jie Xue Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles
Jonathan Conroy and Csaba Toth Hop-Spanners for Geometric Intersection Graphs
Jean Chartier and Arnaud de Mesmay Finding weakly simple closed quasigeodesics on polyhedral spheres
Martin Balko, Manfred Scheucher and Pavel Valtr Erdős-Szekeres-type problems in the real projective plane
Mitchell Black, Nello Blaser, Amir Nayyeri and Erlend Raa Vågset ETH-tight algorithms for finding surfaces insimplicial complexes of bounded treewidth
Gábor Damásdi and Dömötör Pálvölgyi Three-chromatic geometric hypergraphs
Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber, Rosna Paul, Patrick Schnider, Raphael Steiner, Tim Taubner and Birgit Vogtenhuber Edge Partitions of Complete Geometric Graphs
Anne Driemel, Ivor van der Hoog and Eva Rotenberg On the Discrete Fréchet Distance in a Graph
Niloufar Fuladi, Alfredo Hubard and Arnaud de Mesmay Short topological decompositions of non-orientable surfaces
Don Sheehy and Siddharth Sheth Nearly-Doubling Spaces of Persistence Diagrams
Haim Kaplan, Alexander Kauer, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty and Paul Seiferth Dynamic Connectivity in Disk Graphs
Paul Jungeblut, Linda Kleist and Tillmann Miltzow The Complexity of the Hausdorff Distance
Anders Aamand, Mikkel Abrahamsen, Thomas Ahle and Peter Michael Reichstein Rasmussen Tiling with Squares and Packing Dominos in Polynomial Time
Ahmad Biniaz Acute Tours in the Plane
Cameron Rudd, Nathan Dunfield and Malik Obeidin Computing a link diagram given its exterior
Wai Ming Tai Optimal Coreset for Gaussian Kernel Density Estimation
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou and Kirill Simonov Parameterized Algorithms for Upward Planarity
Salman Parsa and Tim Ophelders Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals
Janos Pach, Gabor Tardos and Geza Toth Disjointness graphs of short polygonal chains
Tamal K. Dey, Woojin Kim and Facundo Mémoli Computing Generalized Rank invariant for 2-Parameter Persistence Modules via Zigzag Persistence and its Applications
Thekla Hamm and Petr Hlineny Parameterised Partially-Predrawn Crossing Number
Peyman Afshani and Pingan Cheng On Semialgebraic Range Reporting
Lily Chung, Erik D. Demaine, Dylan Hendrickson and Victor Luo Flat Folding an Unassigned Single-Vertex Complex (Plane Graph with Specified Edge Lengths) without Flat Angles
Magnus Bakke Botnan, Steffen Oppermann and Steve Oudot Signed Barcodes for Multi-Parameter Persistence via Rank Decompositions
Francis Lazarus and Florent Tallerie A Universal Triangulation for Flat Tori
Oswin Aichholzer, Alfredo Garcia, Javier Tejel, Birgit Vogtenhuber and Alexandra Weinberger Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs
Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto and Stijn Slot Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Jürgen Kusche, Elmar Langetepe, Philip Mayer, Petra Mutzel and Heiko Röglin Minimum-Error Triangulations for Sea Surface Reconstruction
Hung Le, Lazar Milenkovic and Shay Solomon Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound
Tamal Dey, Michał Lipiński, Marian Mrozek and Ryan Slechta Tracking Dynamical Features via Continuation and Persistence
Zuzana Patáková and Micha Sharir Covering points by hyperplanes and related problems
Marc Glisse and Siddharth Pritam Swap, Shift and Trim to Edge Collapse a filtration
Marco Contessoto, Facundo Mémoli, Anastasios Stefanou and Ling Zhou Persistent cup-length
Yitzchak Solomon, Alexander Wagner and Paul Bendich From Geometry to Topology: Inverse Theorems for Distributed Persistence
Dominique Attali and Andre Lieutier Delaunay-like triangulation of smooth orientable submanifolds by least L1-norm minimization
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh and Jie Xue True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs
Pankaj Agarwal, Boris Aronov, Esther Ezra, Matthew Katz and Micha Sharir Arc-Intersection Queries Amid Triangles in Three Dimensions and Related Problems
Zdenek Dvorak, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan and Torsten Ueckerdt On comparable box dimension
Chaya Keller and Micha A. Perles An (ℵ0,k+2)-Theorem for k-Transversals
Mincheol Kim, Chanyang Seo, Taehoon Ahn and Hee-Kap Ahn Farthest-point Voronoi diagrams in the presence of rectangular obstacles
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx and André Nusser Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Ulrich Bauer and Fabian Roll Gromov hyperbolicity, geodesic defect, and apparent pairs in Rips filtrations
Ulrich Bauer, Håvard Bjerkevik and Benedikt Fluhr Quasi-universality of Reeb graph distances
Erin Chambers, Salman Parsa and Hannah Schreiber On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class
Alexandros Eskenazis ε-isometric dimension reduction for incompressible subsets of ℓp
Daniel Rutschmann and Manuel Wettstein Chains, Koch Chains, and Point Sets with many Triangulations
Nicolas Grelier Hardness and Approximation of Minimum Convex Partition
Alexander Rolle The degree-Rips complexes of an annulus with outliers
Yair Bartal, Ora Nova Fandina and Kasper Green Larsen Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures
Kevin Buchin, André Nusser and Sampson Wong Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time
Fan Wang, Hubert Wagner and Chao Chen GPU Computation of the Euler Characteristic Curve for Imaging Data