Point Separation Problems in the Plane: Improved Upper and Lower Bounds
Jack Spalding-Jamieson, Anurag Murty Naredla
Point Separation Problems in the Plane
Jack Spalding-Jamieson
Part 1: Improved Upper and Lower Bounds (with Anurag Murty Naredla)
ESA 2025
Part 2: Subquadratic Approximation Algorithms (with Jayson Lynch)
Preprint
Point Separation: Problem
Input: Two points $s,t\in\mathbb{R}^2$ and obstacles $\mathcal{C}$
Output: Minimum-weight set in $\mathcal{C}$ whose union separates $s$ and $t$
Models
Specific objects: Obstacles from a fixed family (e.g., disks, unit disks, line segments).
Arrangement model: Build arrangement $D$ of obstacles; reason on its vertices/edges.
Oracle model: Assume existence of oracle that says if two objects intersect, and also relates to $s$ and $t$.
Oracle
Fix canonical points $x_{\gamma}$ for each obstacle $\gamma$, and a path $\pi$ from $s$ to $t$.
Input: $\gamma_1,\gamma_2$, value $b\in\{0,1\}$
Output: Path exists from $x_{\gamma_1}$ to $x_{\gamma_2}$ in $\gamma_1\cup\gamma_2$ crossing $\pi$ $b$ times, modulo $2$?
Results: Arrangement and Oracle Models
| Model | Weights | Previous | Our Result | Lower Bounds |
|---|---|---|---|---|
| Oracle | Yes | $O(n^3)$ | $\widetilde{O}(n^{(3+\omega)/2})$ | $\Omega^*(n^2)$ |
| Oracle | No | $O(n^3)$ | $O(n^\omega\log n)$ | $\Omega^*(n^{3/2})$ |
| Arrangement | Yes | $O(km^2\lg k)$ | $O(km+k^2\lg k)$ | $\Omega^*(km)$ |
$\omega \approx 2.373$. $k$ = arrangement vertices; $m$ = obstacle–vertex incidences.
High-level method: Reduce to APSP in a special graph.
Results: Unweighted Specific Objects
| Object Type | Previous | Our Result | Lower Bounds |
|---|---|---|---|
| Segments | $O(n^3)$ | $O(n^{7/3}\log^{1/3}n)$ | $\Omega^*(n^{3/2})$ |
| Axis-aligned segments | $O(n^3)$ | $O(n^2\log\log n)$ | None |
| Disks | $O(n^3)$ | $O(n^2\log n)$ | None |
| Unit disks | $O(n^2\log^3 n)$ | $O(n^2\log n)$ | None |
High-level method: Solve static intersection problems in the "homology cover space".
Results: Weighted Specific Objects
| Object Type | Previous | Our Result | Lower Bounds |
|---|---|---|---|
| Segments | $O(n^3)$ | $\widetilde{O}(n^{7/3})$ | $\Omega^*(n^2)$ |
| Axis-aligned segments | $O(n^3)$ | $\widetilde{O}(n^2)$ | None |
| Rectilinear polylines | $O(n^3)$ | $\widetilde{O}(n^2)$ | $\Omega^*(n^2)$ |
High-level method: Biclique covers for sparse graph representation.
Geometric Intersection Graphs
Geometric Intersection Graph:
- Vertices: Geometric objects (e.g. disks)
- Edges: Pairwise-intersecting geometric objects
Equivalent definition:
- Vertices: Specified points on each geometric object
- Edges: Path exists through object pair between specified points
Point-in-Polygon Characterization
Ray crosses polygon odd # times ⟺ point inside
Point-Pair Separation by Polygon
Segment crosses polygon odd # times ⟺ polygon separates endpoints
Path crosses polygon odd # times ⟺ polygon separates endpoints
Path crosses curve odd # times ⟺ curve separates endpoints
Point Separation is a Curve-Finding Problem
The Homology Cover Space
The plane
The plane (no \(s\) or \(t\))
The plane (no \(s\) or \(t\))
\( \mathbb{R}^2 \)
\( \mathbb{R}^2 \setminus \{s,t\} \)
Connectivity: Normal
The homology cover space
\(\left(\mathbb{R}^2 \setminus \{s,t\}\right) \times \{0,1\}\)
Connectivity: Normal, except at \( \pi \)
Walking around in the Homology Cover Space
$\pi$ is a portal.
The Homology Cover Space: Portal Construction
Obstacles connect through portals between the two copies
Non-Separating Curves in the Plane/Homology Cover
Separating Curves in the Plane/Homology Cover
Mapping an object into the Homology Cover
Each object in the plane induces 2 objects in the homology cover.
Obstacles in the Homology Cover: Oracle Ver.
This is a new geometric intersection graph!
Call it $\overline{G}$.
The Oracle Model
Oracle
Fix canonical points $x_{\gamma}$ for each obstacle $\gamma$, and a path $\pi$ from $s$ to $t$.
Input: $\gamma_1,\gamma_2$, value $b\in\{0,1\}$
Output: Path exists from $x_{\gamma_1}$ to $x_{\gamma_2}$ in $\gamma_1\cup\gamma_2$ crossing $\pi$ $b$ times, modulo $2$?
Equivalently, oracle model gives edges of $\overline{G}$.
Key Theorem (Homology Cover)
Each vertex in $\overline{G}$ corresponds to some obstacle in the original point-separation problem.
Two such vertices exist for each obstacle.
Theorem
For two vertices $v,v'\in\overline{G}$ corresponding to the same initial object $c$, let $d_c$ be their distance in $\overline{G}$.
Then the solution to the point-separation problem is exactly $\min_c d_c$.
Suffices to compute $n$ distances in $\overline{G}$.
$\implies$Suffices to solve APSP over $\overline{G}$.
Unweighted Specific Objects with Static Intersection
Static Intersection Problem
Given two fixed sets $A,B$, report for each $a\in A$ whether it intersects any $b\in B$ (static inputs). Let $\text{SI}(n,m)$ be the total time ($|A|=n,|B|=m$).
Theorem (Chan & Skrepetos)
For an unweighted geometric intersection graph $G$ induced by objects $\mathcal{C}$, APSP can be solved in $O(n\cdot\text{SI}(n,n))$ time.
Known results (in the plane):
| Obstacle Class | $\text{SI}(n,n)$ |
|---|---|
| General Disks | $O(n \log n)$ |
| Axis-Aligned Line Segments | $O(n \log \log n)$ |
| Arbitrary Line Segments | $O(n^{4/3} \log^{1/3} n)$ |
We want to get the same results in the homology cover space.
Static Intersection in the Homology Cover
General idea: Reduce to the planar case by splitting along $\overline{st}$.
Split line segments are still line segments ⟹ reduce to two planar cases.
Disks: More complicated. Reduce to four planar cases.
Static Intersection of Disks in the Homology Cover
(projection of all objects into plane)
base set in blue, query set in red
look at only one copy of the "plane" at a time
split up top/bottom of that copy via line passing through $\overline{st}$
Take boundary of base set
Take boundary of base set
Use point-location for query responses
Total time: $\text{SI}(n,n) = O(n\log n)$.
Weighted Specific Objects: What is a Biclique Cover?
Biclique
Size: $5+5=10$
Sparsified Biclique
Edges: biclique size $\times2$
A biclique cover is a set of biclique subgraphs whose union is $\overline{G}$.
Size = sum of biclique sizes.
Small biclique cover = sparse graph preserving vertex-weighted shortest-paths! Run Dijkstra.
Weighted Specific Objects: Biclique Cover Size Example
Line segment intersection graph. Biclique cover size?
Biclique cover size? $9+4=13$
Weighted Specific Objects: Biclique Cover Size Bounds
Plane
| Obstacle Class | Biclique Cover |
|---|---|
| Axis-Aligned Line Segments | $O(n \text{ polylog } n)$ |
| Arbitrary Line Segments | $O(n^{4/3} \text{ polylog } n)$ |
| Unit Disks | $O(n^{4/3} \text{ polylog } n)$ |
| General Disks | $O(n^{4/3} \text{ polylog } n)$ |
Homology Cover
| Obstacle Class | Biclique Cover |
|---|---|
| Axis-Aligned Line Segments | $O(n \text{ polylog } n)$ |
| Arbitrary Line Segments | $O(n^{4/3} \text{ polylog } n)$ |
| Unit Disks | Open |
| General Disks | Open |
Point-separation time complexity: $O(\text{biclique cover size} \cdot n \log n)$
Lower Bound Construction
- Reduce from min-weight triangle or sparse $k$-cycle/$k$-walk.
- Create obstacle for each edge of input graph.
- $k$-clique conjecture $\Rightarrow$ $\Omega(n^{2-\varepsilon})$ (weighted line segments)
- 3SUM conjecture $\Rightarrow$ $\Omega(n^{3/2-\varepsilon})$ (unweighted line segments)
Proof Method
Open Problems
Open Problems:
- Better than $O(n^3)$ for weighted disks/unit disks?
- Likely doable with a specialized biclique cover via similar method to static intersection testing
- $O(n^{2-\varepsilon})$ for any case?
- Likely possible in $O(n^{2-\frac{1}{20}})$ for unit disks via a FOCS 2025 paper
- All other cases completely open (e.g. unweighted axis-aligned line segments)
- $\tilde{O}(n^{7/3-\varepsilon})$ for unweighted line segments? (bypass Hopcroft's)
- $\tilde{O}(n^{2.5-\varepsilon})$ time for min-distance problem? (harder)
- Given $O(n)$ pairs $(a_i,b_i)$ in a graph $G$, find $\min_i d_G(a_i,b_i)$.
- Approximation-algorithms for multiple $(s,t)$ pairs
- "Generalized point-separation" is very hard, fast exact and FPT algorithms likely impossible.
Fin...?
Summary: Reduce to shortest-path problem in homology cover space
Questions?
Part 2: Subquadratic Approximations
Breaking the Quadratic Barrier for Unweighted Objects
- Limitation: Reductions to APSP have $\Omega(n^2)$ barrier
- Open Question: Can an exact algorithm beat quadratic time?
- Easier Question: Can an approximation algorithm beat quadratic time?
- Answer (for certain unweighted convex objects): Yes — via divide-and-conquer
Approximation Results
| Object Type | Running Time | Randomized? |
|---|---|---|
| Approximation Guarantee: OPT+1 | ||
| Disk | $O(n^{3/2} (\log n)^2)$ | Monte Carlo (w.h.p.) |
| Line segment | $\tilde{O}(n^{11/6})$ | Monte Carlo (w.h.p.) |
| Rectilinear line segment | $O(n^{3/2} (\log n)^2)$ | Monte Carlo (w.h.p.) |
| Approximation Guarantee: $(1+\varepsilon)$ OPT+1 | ||
| Disk | $O\left( \frac{n (\log n)^3}{\varepsilon^2} \right)$ | Deterministic |
| Line segment | $\tilde{O}\left( \frac{n^{4/3}}{\varepsilon^2} \right)$ | Deterministic |
| Rectilinear line segment | $O\left( \frac{n (\log n)^3}{\varepsilon^2} \right)$ | Deterministic |
All runtimes are subquadratic!
Fundamental Ideas for Approximation
Key Theorem (restated): The solution to point-separation is exactly $\min_c d_c$, where $d_c$ is the distance between two vertices in $\overline{G}$ corresponding to object $c$.
- We will approximate $d_c$ for every object $c$, rather than compute it exactly.
- To get an optimum solution to point-separation: suffices to identify any object in an optimal solution.
- To get a +1 approximation: suffices to identify any object in 1-neighbourhood of an optimal solution.
- Similar principle applies for weaker approximations.
Monte Carlo Algorithm
Recall: To get an optimum solution to point-separation, suffices to identify any object in an optimal solution.
Key Insight:
- Bigger solution = easier to find with random sampling
- Use Monte Carlo filter to detect large OPT early
Monte Carlo Theorem
Each iteration takes $\text{SP}(n)$ time. If separating set $C$ exists, with high probability find $C'$ with $|C'| \leq |C|$ in $O\left(\frac{|C|}{n}\log n\right)$ iterations.
Useful for detecting if $|C| = O(\sqrt{n})$ exists within $O(\sqrt{n}\log n)$ iterations.
Figure: Divide-and-Conquer over $\overline{st}$
Inspiration: Reif's algorithm for planar min-cut
Dividing Paths
Time to find initial path: $O(1)$ SSSP computations in $\overline{G}$
Time to check path lengths: $O(\sqrt{n})$ SSSP computations in $\overline{G}$
Recurse into first short path: Perform $O(\text{length}) = O(\sqrt{n})$ SSSP computations
Time Complexity Analysis
Total Time Complexity:
$O(\sqrt{n}\log n)$ SSSP computations
levels
collection using
$O(\sqrt{n})$ SSSP computations
$O(\sqrt{n}\log n)$ SSSP computations
| Object Type | Running Time |
|---|---|
| Approximation Guarantee: OPT+1 | |
| Disk | $O(n^{3/2} (\log n)^2)$ |
| Line segment | $\tilde{O}(n^{11/6})$ |
| Rectilinear line segment | $O(n^{3/2} (\log n)^2)$ |
$(1+\varepsilon)$OPT+1 approximations: Recursive dividing path routine
Fin!
Summary: Subquadratic approximation algorithms for point-separation via divide-and-conquer
Questions?