This special issue of Discrete & Computational Geometry contains a selection of papers presented at the 38th International Symposium on Computational Geometry (SoCG 2022) held in Berlin, on June 7–10, 2022, as part of the Computational Geometry Week (CGWeek 2022). Altogether, 174 papers were submitted to SoCG2022, among which the program committee selected 64 papers to be presented at the conference. The ten papers in this issue were invited because they received a strong support within the program committee and provide a sample of the excellent research presented at the conference in a broad range of topics.

The papers from this issue were invited, submitted, reviewed, and revised according to the usual high standards of D &CG. We thank the authors of all the submitted papers for revising and polishing their work. We are very grateful to the anonymous referees for their dedication, expertise, and effort that ensure the high quality of the papers in this special issue. We also thank Ken Clarkson, co-Editor-in-Chief of D &CG, for guiding us through the process of composing this special issue.

The articles appear in this special issue in alphabetical order of the names of the first authors. In the remainder of this foreword we briefly introduce each paper in the same order.

The paper On Semialgebraic Range Reporting by Peyman Afshani and Pingan Cheng studies range query questions in a very general form, asking to efficiently report the points that satisfy a set of semi-algebraic queries. The paper builds on recent breakthroughs in that area and shows a lower bound for the case of fast queries that essentially matches the existing upper bound. They also show that an existing lower bound in the planar case is tight by achieving the same upper bound for a uniformly distributed point set.

In geometric graph theory, a 35-year old conjecture by Rafla asserts that every simple drawing of the complete graph \(K_n\) in the plane contains a noncrossing hamiltonian cycle. The paper Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs by Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger sheds new light on this problem by introducing and analyzing a new type of drawings that captures, up to homeomorphism, properties of general drawings, and proves that every simple drawing of \(K_n\) in the plane contains \(\Omega (\sqrt{n})\) pairwise disjoint edges and a noncrossing path of length \(\Omega \hspace{0.44434pt}(\log n/{\log \log n})\).

Two-parameter persistent homology is notoriously challenging. The paper Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and its Applications by Tamal Dey, Woojin Kim, and Facundo Mémoli describes an algorithm to compute the generalized rank over an interval in a 2-parameter persistence module using a single 1-parameter zigzag. This reduction from two parameters to a single (zigzag) parameter is a big step towards practical applicability.

A famous theorem of Lyusternik and Schnirelmann asserts that any Riemannian sphere admits at least three distinct simple closed geodesics, and a similar result was established by Pogorelov in 1949 for polyhedral spheres when geodesics are relaxed into quasigeodesics. The existence of a finite algorithm for computing a quasigeodesic of a given polyhedral sphere has been open for more than 30 years. The paper Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres by Jean Chartier and Arnaud de Mesmay gives such an algorithm and extends Pogorelov’s theorem to the non-convex and non-embedded setting.

In low-dimensional topology, constructing the diagram of a link from a triangulation of its exterior is a computationally hard problem. The paper ‘Computing a Link Diagram from its Exterior by Nathan Dunfield, Malik Obeidin, and Cameron Rudd presents effective new techniques that solve this problem for input sizes relevant in practice.

The famous Johnson–Lindenstrauss Lemma asserts that any n-point subset of \(\ell _2\) embeds with small multiplicative distortion into \(\ell _2^d\), where d is logarithimic in n. The paper \(\epsilon \) -Isometric Dimension Reduction for Incompressible Subsets of \(\ell ^p\) by Alexandros Eskenazis shows that a similar result holds in \(\ell _p\) for any \(1< p < \infty \), when one considers additive distortion and requires the point set to have bounded \(\ell _p\)-norm. This is one of the first dimension-reduction results in \(\ell _p\) for \(p \notin \{1,2,\infty \}\).

The paper The Complexity of the Hausdorff Distance by Paul Jungeblut, Linda Kleist, and Tillmann Miltzow uses quantitative results on effective quantifier elimination in the first order theory of the reals to show that computing the Hausdorff distance between semi-algebraic sets is complete for the strict universal existential theory of the real complexity class.

The paper Dynamic Connectivity in Disk Graphs by Haim Kaplan, Alexander Kauer, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roddity, and Paul Seiferth studies the dynamic graph connectivity problem for the special case of disk graphs. They improve upon previous approaches in terms of space and update time, with the same query time guarantee. They also study the semi-dynamic setup where either only insertions or only deletions are allowed, which has not been addressed for disk graphs.

The paper A Universal Triangulation for Flat Tori by Francis Lazarus and Florent Tallerie proves that there exists a triangulation T such that any flat torus is isometric to an embedding of T in three-dimensional space. The existence of T is already non-trivial, and the authors further show that T consists of 2434 triangles and is thus of moderate size.

The celebrated Erdős–Szekeres theorem asserts that any sequence of distinct real numbers contains a large monotone subsequence. The paper A Positive Fraction Erdős–Szekeres Theorem and its Applications by Andrew Suk and Ji Zeng establishes that in fact there always exist many large monotone subsequences. They use this to extend earlier results in geometric Ramsey theory.