Michiel Smid

Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung et al.

Let $S$ be a set of $n$ points in $\mathbb{R}^d$, where $d \geq 2$ is a constant, and let $H_1,H_2,\ldots,H_{m+1}$ be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly $n/m$ points of $S$ are between any two successive hyperplanes. Let $A(S,m)$ be the set of different closest pairs in the ${{m+1} \choose 2}$ vertical slabs that are bounded by $H_i$ and $H_j$, over all $1 \leq i < j \leq m+1$. We prove tight bounds for the largest possible size of $A(S,m)$, over all point sets of size $n$, and for all values of $1 \leq m \leq n$. As a result of these bounds, we obtain, for any constant $ε>0$, a data structure of size $O(n)$, such that for any vertical query slab $Q$, the closest pair in the set $Q \cap S$ can be reported in $O(n^{1/2+ε})$ time. Prior to this work, no linear space data structure with sublinear query time was known.

Anil Maheshwari, Karthik Murali, Michiel Smid

Spanning trees are fundamental for efficient communication in networks. For fault-tolerant communication, it is desirable to have multiple spanning trees to ensure resilience against failures of nodes and edges. To this end, various notions of disjoint or independent spanning trees have been studied, including edge-disjoint, node/edge-independent, and completely independent spanning trees. Alongside these, several Steiner variants have also been investigated, where the trees are required to span a designated subset of vertices called terminals. For instance, the study of edge-disjoint spanning trees has been extended to edge-disjoint Steiner trees; a stronger variant is the problem of internally disjoint Steiner trees, where any two Steiner trees intersect exactly in the terminals. In this paper, we investigate the Steiner analogue of completely independent spanning trees, which we call \emph{completely independent Steiner trees}. A set of Steiner trees is completely independent if, for every pair of terminals $u,v$, the $(u,v)$-paths in all the Steiner trees are internally vertex-disjoint and edge-disjoint. This notion generalizes both completely independent spanning trees and internally disjoint Steiner trees. We provide a systematic study of completely independent Steiner trees from structural, algorithmic, and complexity-theoretic perspectives. In particular, we present several characterisations, connectivity bounds, algorithms, hardness results, and applications to special graph classes such as planar graphs and graphs of bounded treewidth. Along the way, we also introduce a directed variant of completely independent spanning trees via an equivalence with completely independent Steiner trees.