$\left(1+\tfrac1{k+1}\right)$-approximate point separation $\approx$ $k$-cycle detection

Point-separation instance from the soda2 paper
$\Longrightarrow$
A minimum separating subset highlighted in red
Choose the fewest objects whose union separates $s$ from $t$.
Jayson Lynch  ยท  Jack Spalding-Jamieson
Lower bounds

A directed 3-cycle becomes three separating objects

a b c directed graph s a b c t the three objects form a separating loop

The reduction

Directed $k$-cycle
Directed graph instance
Is there a directed cycle of length $k$?
$\Longrightarrow$
Small point separator
Full layered ray reduction
A line segment in one cone
$\Downarrow$
Its 2-complexity rectilinear replacement
Do at most $k$ polylines separate $s$ and $t$?
separator size $\leq k$ in $T(n)$ $\Longrightarrow$ directed $k$-cycle in $O(T(m))$
$\left(1+\tfrac1{k+1}\right)$-approximate point separation in $T(n)$ $\Longrightarrow$ directed $k$-cycle in $O(T(m))$
Upper bounds

Objects and their intersection graph in the homology cover

Objects in two homology-cover sheets and their planar projection

From additive to multiplicative

Additive $+1$ approximation
Monte Carlo
algorithm
+
Divide & conquer
$O(\log n)$
levels
$\times$
dividing-path
routine
=
$\mathrm{OPT}+1$
Exact for $\mathrm{OPT}\leq k$
using directed $k$-cycle
Together:  $\left(1+\dfrac1{k+1}\right)$-approximation
Lower bound
$\left(1+\tfrac1{k+1}\right)$-approximate point separation in $T(n)$ $\quad\Longrightarrow\quad$ directed $k$-cycle in $O(T(m))$
directed $k$-cycle $\quad\Longleftrightarrow\quad$ $\left(1+\tfrac{1}{k+1}\right)$-approximate point separation