- Design, analysis, and implementation of geometric algorithms and data structures;
- Computational complexity of geometric problems;
- Implementation and experimental evaluation of geometric algorithms and heuristics, including mathematical, numerical, and algebraic aspect;
- Discrete and combinatorial geometry;
- Computational topology, topological data analysis, and topological combinatorics;
- Applications of computational geometry or topology in any field.

## Call for papers: 39th SoCG

The 39th International Symposium on Computational Geometry (SoCG 2023) is planned to be held in Dallas, Texas, June 12-15 2023, as part of the Computational Geometry (CG) Week. We invite high quality submissions that describe original research on computational problems in a geometric and/or topological setting. Topics of interest include, but are not limited to:

## Important Dates

**25 November 2022:**Abstracts due (23:59 AoE (anywhere on Earth))**02 December 2022:**Papers due (23:59 AoE (anywhere on Earth))**07 February 2023:**Notification of acceptance/rejection**16 March 2023:**Final versions of accepted papers due**11 June 2023:**Welcome reception in the evening**12-15 June 2023:**Symposium

SoCG 2023 HotCRP submission page

## 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 in HotCRP. You are also welcome to contact a SoCG SafeTOC advocate who will treat any supporting information confidentially. For a list of SoCG advocates with contact information, please refer to CG Week Code of Conduct.

## Submission Guidlines

**Paper types**

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.-
__Mathematical Foundations__: A typical paper will contain theorems and proofs describing new results in discrete or combinatorial geometry, discrete differential geometry or topology, or in topological combinatorics. The paper will primarily be evaluated on its technical depth, the importance of the results, the elegance of the solution, the connection of the problem studied to computational geometry and topology, and the potential future impact on algorithm development.__Algorithmic Complexity__: A typical paper will contain algorithms, data structures, theorems, proofs, or lower bound constructions describing new results on computational geometry problems. The paper will primarily be evaluated on the (mathematical or computational) relevance and importance of the problem studied, its technical depth, the elegance of the solution, and the potential future impact of the results or the proposed new methods and techniques.__Experiments and Implementation__: A typical paper will make a clear contribution to the implementation and evaluation of geometric algorithms, such as exact, approximate, or algebraic computation, algorithms engineering, or the experimental evaluation of competing algorithmic approaches. The paper will primarily be evaluated on the completeness and the expected impact of the proposed implementation, the soundness of the experiments, the quality and quantity of testing, and on the general amount of knowledge gained.__Applications__: A typical paper will describe the modeling and algorithmic choices made when developing or adapting computational geometry techniques for an application area. The paper will be primarily evaluated on the soundness of the modeling decisions, the ingenuity of the solution, the effectiveness of the proposed method, and the expected impact in the application area. One might also consider the lesson learned regarding the applicability or suitability of computational geometry tools to the specific area.

**Double Blind and PC submissions**

For the first time, this year's SoCG will employ a lightweight double-blind reviewing process, and will allow PC members (other than the PC chairs) to submit to the conference as well. Submissions should not reveal the identity of the authors in any way. In particular, authors' names, affiliations, and email addresses should not appear at the beginning or in the body of the submission. Authors should ensure that any references to their own related work is in the third person (e.g., not "We build on our previous work ..." but rather "We build on the work of ..."). Particular care needs to be taken if there is any accompanying software or data, which needs to be linked anonymously (for example, via a DropBox folder or Anonymous GitHub, perhaps with a subset of synthetic data if the real data is not anonymized). Upon registering a submission, the authors will declare conflicts of interest with PC members, as well as listing email address or domain level conflicts (i.e. “Erin Chambers (Saint Louis University)”, “All (University of Sydney)”.) of other professional or personal conflicts. The purpose of lightweight double-blind reviewing is to help PC members and external reviewers come to an initial judgment about the paper without bias, not to make it impossible for them to discover the authors if they were to try. Authors should feel free to disseminate their ideas or draft versions of their paper as they normally would. For example, authors may post drafts of their papers on the web, submit them to arXiv, and give talks on their research ideas. We encourage authors with further questions on double-blind reviewing to contact the PC chairs, or to see the more detailed discussion in the proposal that preceded the vote to move to double blind: https://computational-geometry.org/documents/Double_blind_proposal.pdf**Format**

Submissions must be formatted in accordance with the LIPIcs proceedings guidelines. Authors must use the new LaTeX class file socg-lipics-v2021.cls (version 0.9), with the option “anonymous”; note that the cls file is a wrapper around the standard LIPIcs class. The LIPIcs style and instructions are available here; the 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), 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 not to exceed 500 lines even if some lines are not counted automatically.**Contents of the submission**

Papers should be submitted in the form of an extended abstract, which begins with the title of the paper, 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.**Appendix and additional data**

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.**Previous or simultaneous submission**

Previous or simultaneous submissions 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.**Strict guidelines**

Submissions deviating from the above guidelines risk being rejected without further consideration.**Guidelines for reviewers**

The guidelines are available here.

## Accepted Papers

**Presentation, awards, and special issues**

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.**Format**

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.

## Program Committee

- Anastasios Sidiropoulos, University of Illinois at Chicago, USA
- André Nusser, University of Copenhagen, Denmark
- Arijit Ghosh, Indian Statistical Institute, India
- Arindam Khan, IISc Bangalore, India
- Arnaud de Mesmay, CNRS, France
- Balázs Keszegh, Alfréd Rényi Institute of Mathematics, Hungary
- Benjamin Burton, University of Queensland, Australia
- Elena Arseneva, Università della Svizzera italiana, Switzerland
- Elizabeth Munch, Michigan State University, USA
- Erin Chambers, co-chair, Saint Louis University, USA
- Esther Ezra, Bar Ilan University, Israel
- Facundo Mémoli, Ohio State University, USA
- Günter Rote, Freie Universität Berlin, Germany
- Ileana Streinu, Smith College, USA
- Jack Snoeyink, University of North Carolina, USA
- Jeff Erickson, University of Illinois Urbana-Champaign, USA
- Joachim Gudmundsson, co-chair, University of Sydney, Australia
- Joseph S. B. Mitchell, Stony Brook University, USA
- Ken Clarkson, IBM Almaden Research, USA
- Kevin Verbeek, TU Eindhoven, the Netherlands
- Konrad Swanepoel, London School of Economics, UK
- Linda Kleist, Technische Universität Braunschweig, Germany
- Maarten Löffler, Utrecht University, the Netherlands
- Mathijs Wintraecken, Institute of Science and Technology, Austria and Inria Sophia
- Antipolis Méditerranée, France
- Matias Korman, Siemens Electronic design automation, USA
- Matya Katz, Ben-Gurion University, Israel
- Oswin Aichholzer, Graz University of Technology, Austria
- Pat Morin, Carleton University, Canada
- Patrizio Angelini, John Cabot University, Italy
- Saket Saurabh, IMSc Chennai, India
- Uli Wagner, Institute of Science and Technology, Austria
- Valentin Polishchuk, Linköping University, Sweden
- Yoshio Okamoto, The University of Electro-Communications, Japan

## List of Accepted Papers

- "Maximum overlap area of a convex polyhedron and a convex polygon under translation" by H. Zhu and H. J. Kweon
- "Distinguishing classes of intersection graphs of homothets or similarities of two convex disks" by M. Abrahamsen and B. Walczak
- "New Approximation Algorithms for Touring Regions" by R. Qi, B. Qi, and X. Chen
- "The Christoffel-Darboux kernel for topological data analysis" by P. Roos Hoefgeest and L. Slot
- "Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time" by D. Eppstein
- "Reconfiguration of colorings in triangulations of the sphere" by T. Ito, Y. Iwamasa, Y. Kobayashi, S. Maezawa, Y. Nozaki, Y. Okamoto, and K. Ozeki
- "On Helly numbers of exponential lattices" by G. Ambrus, M. Balko, N. Frankl, A. Jung, and M. Naszódi
- "Shortest Paths in Portalgons" by M. Löffler, T. Ophelders, R. I. Silveira, and F. Staals
- "The Complexity of Geodesic Spanners" by S. de Berg, M. van Kreveld, and F. Staals
- "Algorithms for length spectra of combinatorial tori" by V. Delecroix, M. Ebbens, F. Lazarus, and I. Yakovlev
- "On higher dimensional point sets in general position" by A. Suk and J. Zeng
- "Finding large counterexamples by selectively exploring the Pachner graph" by B. Burton and A. He
- "Improved Algebraic Degeneracy Testing" by J. Cardinal and M. Sharir
- "An extension theorem for signotopes" by H. Bergold, S. Felsner, and M. Scheucher
- "Efficient Computation of Image Persistence" by U. Bauer and M. Schmahl
- "Efficient Two-Parameter Persistence Computation via Cohomology" by U. Bauer, M. Lesnick, and F. Lenzen
- "Meta-Diagrams for 2-Parameter Persistence" by N. Clause, T. K. Dey, F. Memoli, and B. Wang
- "Disjoint faces in simple drawings of the complete graph and topological Heilbronn problems" by A. Hubard and A. Suk
- "Topological Universality of the Art Gallery Problem" by J. Stade and J. Tucker-Foltz
- "Slice, simplify and stitch: topology-preserving simplification scheme for massive voxel data" by H. Wagner
- "Geometric Embeddability of Complexes is $\exists\R$-complete" by M. Abrahamsen, L. Kleist, and T. Miltzow
- "The Number of Edges in Maximal 2-planar Graphs" by M. Hoffmann and M. M. Reddy
- "Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings" by J. Holm, I. van der Hoog, and E. Rotenberg
- "Multilevel Skeletonization Using Local Separators" by J. A. Bærentzen, R. E. Christensen, E. T. Gæde, and E. Rotenberg
- "Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable" by S. Bhore, R. Ganian, L. Khazaliya, F. Montecchiani, and M. Nöllenburg
- "On the Width of Complicated JSJ Decompositions" by K. Huszár and J. Spreer
- "Ephemeral persistence features and the stability of filtered chain complexes" by F. Mémoli and L. Zhou
- "Computing a Dirichlet domain for a hyperbolic surface" by V. Despré, B. Kolbe, H. Parlier, and M. Teillaud
- "The Parameterized Complexity of Coordinated Motion Planning" by E. Eiben, R. Ganian, and I. Kanj
- "A generalization of the persistent Laplacian to simplicial maps" by A. B. Guelen, F. Memoli, Z. Wan, and Y. Wang
- "Computing Instance Optimal Kernels in Two Dimensions" by P. K. Agarwal and S. Har-Peled
- "The Geodesic Edge Center of a Simple Polygon" by A. M. Naredla and A. Lubiw
- "Improved Bounds for Covering Paths and Trees in the Plane" by A. Biniaz
- "Decomposition of zero-dimensional persistence modules via rooted subsets" by Á. J. Alonso and M. Kerber
- "Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings" by A. Filtser
- "Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d >= 4" by E. Gorbachev and M. Künnemann
- "Line Intersection Searching Amid Unit Balls in 3-Space" by P. Agarwal and E. Ezra
- "FibeRed: Fiberwise Dimensionality Reduction of Topologically Complex Data with Vector Bundles" by L. Scoccola and J. A. Perea
- "Toroidal Coordinates: Decorrelating Circular Coordinates With Lattice Reduction" by L. Scoccola, H. Gakhar, J. Bush, N. Schonsheck, T. Rask, L. Zhou, and J. A. Perea
- "Finding a Maximum Clique in a Disk Graph" by J. A. Espenant, J. M. Keil, and D. Mondal
- "Combinatorial Depth Measures for Hyperplane Arrangements" by P. Schnider and P. Soberon
- "Random projections for curves in high dimensions" by I. Psarros and D. Rohde
- "The localized Union-of-Balls Bifiltration" by M. Kerber and M. Söls
- "Sparse higher order Čech filtrations" by B. Boeira Dornelas, M. Kerber, and M. Buchet
- "Drawings of complete multipartite graphs up to triangle flips" by M. Hoffmann, O. Aichholzer, M. Chiu, H. Hoang, Y. Maus, J. Kynčl, B. Vogtenhuber, and A. Weinberger
- "Linear size universal point sets for classes of planar graphs" by S. Felsner, H. Schrezenmaier, F. Schröder, and R. Steiner
- "Lower Bounds for Intersection Reporting among Flat Objects" by P. Afshani and P. Cheng
- "Coresets for Clustering in Geometric Intersection Graphs" by S. Bandyapadhyay, F. Fomin, and T. Inamdar
- "Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set" by A. Khan, A. Lonkar, S. Rahul, A. Subramanian, and A. Wiese
- "Voronoi Diagrams in the Hilbert Metric" by A. Gezalyan and D. Mount
- "Minimum-Membership Geometric Set Cover, Revisited" by S. Bandyapadhyay, W. Lochet, S. Saurabh, and J. Xue
- "FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii" by S. Bandyapadhyay, W. Lochet, and S. Saurabh
- "A structural approach to tree decompositions of knots and spatial graphs" by C. Lunel and A. de Mesmay
- "On the geometric thickness of 2-degenerate graphs" by R. Jain, M. Ricci, J. Rollin, and A. Schulz
- "Voronoi-like graphs - towards extending Delaunays theorem and applications" by E. Papadopoulou
- "Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size" by T. M. Chan and Z. Huang
- "Minimum $L_\infty$ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem" by T. M. Chan
- "Sparse Euclidean Spanners with Optimal Diameter: A General Robust Lower Bound Via a Concave Inverse-Ackermann Function" by H. Le, L. Milenkovic, and S. Solomon
- "Optimal Volume-Sensitive Bounds for Polytope Approximation" by S. Arya and D. Mount
- "Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs" by E. Galby, A. Munaro, and S. Yang
- "When ternary triangulated disc packings are densest: examples, counter-examples and techniques" by D. Pchelina and T. Fernique