For some geometric graph classes, tractability of testing first-order formulas is precisely characterised by the graph parameter twin-width. This was first proved for interval graphs among others in [BCKKLT, IPEC '22], where the equivalence is called delineation, and more generally holds for circle graphs, rooted directed path graphs, and H-graphs when H is a forest. Delineation is based on the key idea that geometric graphs often admit natural vertex orderings, allowing to use the very rich theory of twin-width for ordered graphs. Answering two questions raised in their work, we prove that delineation holds for intersection graphs of non-degenerate axis-parallel unit segment graphs, but fails for visibility graphs of 1.5D terrains. We also prove delineation for intersection graphs of circular arcs.

We investigate machine models similar to Turing machines that are augmented with the operations of a first-order structure $\mathcal{R}$, and we show that under weak conditions on $\mathcal{R}$, the complexity class $Σ_k \mathcal{R}$ may be characterized in four equivalent ways: (1) by polynomial-time algorithms implemented on $\mathcal{R}$-machines together with witness strings, (2) by the $Σ_k\mathcal{R}$-complete problem $Σ_k\text{SAT}(\mathcal{R})$, (3) by the $k$th existential fragment of second-order metafinite logic over $\mathcal{R}$ via descriptive complexity, and (4) via oracles. By characterizing $Σ_k\mathcal{R}$ in these four ways, we extend previous work and embed it in one coherent framework. In addition, we derive similar results for $\exists_k \mathcal{R}$, the constant-free Boolean part of $Σ_k\mathcal{R}$, by showing that $\exists_k\mathcal{R}$ may be characterized in four analogous ways. Some conditions on $\mathcal{R}$ must be assumed in order to achieve the above quaternity because there are infinite-vocabulary structures for which $\text{NP}(\mathcal{R}) = Σ_1 \mathcal{R}$ does not have a complete problem. Surprisingly, even in these cases, we show that $\text{NP}(\mathcal{R})$ does have a characterization in terms of existential second-order metafinite logic, suggesting that descriptive complexity theory is well suited to working with infinite-vocabulary structures, such as real vector spaces.

Given a set of n points in the Euclidean plane, the k-MinSumRadius problem asks to cover this point set using k disks with the objective of minimizing the sum of the radii of the disks. After a long line of research on related problems, it was finally discovered that this problem admits a polynomial time algorithm [GKKPV’12]; however, the running time of this algorithm is O(n881), and its relevance is thereby mostly of theoretical nature. A practically and structurally interesting special case of the k-MinSumRadius problem is that of small k. For the 2-MinSumRadius problem, a near-quadratic time algorithm with expected running time O(n2 log2 n log2 log n) was given over 30 years ago [Eppstein’92]. We present the first improvement of this result, namely, a near-linear time algorithm to compute the 2-MinSumRadius that runs in expected O(n log2 n log2 log n) time. We generalize this result to any constant dimension d, for which we give an O(n2−1/(⌈d/2⌉+1)+ε) time algorithm. Additionally, we give a near-quadratic time algorithm for 3-MinSumRadius in the plane that runs in expected O(n2 log2 n log2 log n) time. All of these algorithms rely on insights that uncover a surprisingly simple structure of optimal solutions: we can specify a linear number of lines out of which one separates one of the clusters from the remaining clusters in an optimal solution.