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:
Submissions must be formatted in accordance with the LIPIcs proceedings guidelines. Authors must use the LaTeX class file socg-lipics-v2021.cls, which is a wrapper around the standard LIPIcs class. The LIPIcs style and instructions are available here; the socg-lipics-v2021.cls class file is available here, and instructions on how to use it are available here. Submissions must not exceed 500 lines, excluding front matter (title, authors, and affiliations), references, and a clearly marked appendix (further described below), but including all other lines (in abstract, algorithms, tables, captions, etc.). The class files provide line counting which should be accurate in most cases. Authors should refrain from putting excessive amounts of text in parts in which lines are not counted automatically. If authors need constructs that contain uncounted lines of text, they should compensate for this by reducing the final line count accordingly. It is the sole responsibility of the authors to not exceed 500 lines even if some lines are not counted automatically.
Papers should be submitted in the form of an extended abstract, which begins with the title of the paper, each author's name and affiliation, as well as a short abstract. This should be followed by the main body of the paper that begins with a precise statement of the problem considered, a succinct summary of the results obtained (emphasizing the significance, novelty, and potential impact of the research), and a clear comparison with related work. The remainder of the extended abstract should provide sufficient details to allow the program committee to evaluate the validity, quality, and relevance of the contribution. Clarity of presentation is very important; the entire extended abstract should be written carefully, taking into consideration that it will be read and evaluated by both experts and non-experts, often under tight time constraints.
All details needed to verify the results must be provided. Supporting materials, including proofs of theoretical claims and experimental details, that do not fit in the 500-line limit should be given in an appendix. If more appropriate, the full version may be given as the appendix. In both cases, however, the authors should include in the main part specific pointers to the relevant locations in the appendix. The appendix will be read by the program committee members and subreviewers at their discretion and will not be published as part of the proceedings. Thus, the paper without the appendix should be able to stand on its own. Experimental and implementation results (independent of paper type) must be reproducible and verifiable. Authors of all types of papers are encouraged to put accompanying software and relevant data, if there are any, in a repository accessible to the reviewers. Authors are asked to indicate which of the supporting materials will remain publicly available if their papers are accepted.
Results previously published or accepted for publication in the proceedings of another conference cannot be submitted. Simultaneous submissions of the results to another conference with published proceedings are not allowed. Exempted are workshops and conferences without formal proceedings, but possibly with handouts containing short abstracts. In particular, submissions of papers that have appeared or will be submitted to EuroCG are allowed, since EuroCG does not publish formal proceedings, while submissions of papers that have appeared in CCCG are not allowed. Results that have already been accepted (with or without revision) for publication in a journal at the time of their submission to the symposium are not allowed. A paper submitted to a journal but not yet accepted for publication can be submitted to the symposium. In such cases, the authors must mention this on the front page of the submission and clearly identify the status of the journal submission at the date of the full paper submission deadline.
Submissions deviating from the above guidelines risk being rejected without further consideration.
When writing or evaluating a SoCG paper, it is important to keep in mind that there are different types of contributions, each with its own strengths. To ensure that a submission is evaluated on its own merits, authors will need to identify the main strengths of their submission, as captured by four possible paper types. PC members and external reviewers will be asked to take into account these paper types together with their associated evaluation criteria when they evaluate a paper. There are no quotas for the paper types and submissions can be labeled with more than one paper type at the time of submission.
The guidelines are available here.
Final proceedings versions of accepted papers must respect the same formatting constraints as the submissions (LIPIcs proceedings format with socg-lipics-v2021; 500-line limit, excluding front matter and references), but must not comprise any appendix. If any supporting material (including complete proofs of theoretical claims and experimental details) does not fit in the specified limit, then the full version of the paper containing this information must be referenced in the conference version and made available at a public repository, such as arXiv, by the time the final version is submitted. Where applicable, we encourage the authors to make accompanying software and/or data publicly accessible, with proper references in the paper.
An author of each accepted paper will be expected to attend the symposium and present the paper (approximately 20 minutes). Given the developing COVID-19 pandemic, the format of both attendance and presentation will be clarified closer to the event. Awards will be given for the best paper and for the best student presentation. Authors of a selection of papers from the symposium will be invited to submit extended versions of their papers to special issues of Discrete & Computational Geometry and Journal of Computational Geometry. As in the previous years, the authors of the best paper will be invited to submit an extended version of their paper to Journal of the ACM.
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 https://computational-geometry.org/codeofconduct.html.
|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|