Subquadratic Approximation Algorithms for
Separating Two Points with Objects in the Plane
Jayson Lynch, Jack Spalding-Jamieson
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.
Won't be discussed today.
General (oracle) model: Assume existence of oracle that says if two objects intersect, and gives some information about that intersection.
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$?
Previous Results
| Model | Weights | Upper Bounds | Lower Bounds |
|---|---|---|---|
| General (Oracle) | Yes | $\widetilde{O}(n^{(3+\omega)/2})$ | $\Omega^*(n^2)$ |
| General (Oracle) | No | $O(n^\omega\log n)$ | $\Omega^*(n^{3/2})$ |
High-level method: Reduce to APSP in a special graph.
Previous Results: Unweighted Specific Objects
| Object Type | Upper Bounds | Lower Bounds |
|---|---|---|
| Segments | $O(n^{7/3}\log^{1/3}n)$ | $\Omega^*(n^{3/2})$ |
| Axis-aligned segments | $O(n^2\log\log n)$ | None |
| Disks | $O(n^2\log n)$ | None |
| Unit disks | $O(n^2\log n)$ | None |
Previous Results: Weighted Specific Objects
| Object Type | Upper Bounds | Lower Bounds |
|---|---|---|
| Segments | $\widetilde{O}(n^{7/3})$ | $\Omega^*(n^2)$ |
| Axis-aligned segments | $\widetilde{O}(n^2)$ | None |
| Rectilinear polylines | $\widetilde{O}(n^2)$ | $\Omega^*(n^2)$ |
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
Open Problem
Truly subquadratic algorithms for exact solutions in any class, weighted or unweighted?
(Note: Almost certainly possible for unweighted unit disks via slight generalization of exact distance oracles)
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: The Geometric Intersection Graph
This is a new geometric intersection graph!
Call it $\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}$.
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? | Prev Best (Exact) |
|---|---|---|---|
| Approximation Guarantee: OPT+1 | |||
| Disk | $O(n^{3/2} (\log n)^2)$ | Monte Carlo (w.h.p.) | $O(n^2\log n)$ |
| Line segment | $\tilde{O}(n^{11/6})$ | Monte Carlo (w.h.p.) | $O(n^{7/3}\log^{1/3}n)$ |
| Rectilinear line segment | $O(n^{3/2} (\log n)^2)$ | Monte Carlo (w.h.p.) | $O(n^2\log\log n)$ |
| Approximation Guarantee: $(1+\varepsilon)$ OPT+1 | |||
| Disk | $O\left( \frac{n (\log n)^3}{\varepsilon^2} \right)$ | Deterministic | $O(n^2\log n)$ |
| Line segment | $\tilde{O}\left( \frac{n^{4/3}}{\varepsilon^2} \right)$ | Deterministic | $O(n^{7/3}\log^{1/3}n)$ |
| Rectilinear line segment | $O\left( \frac{n (\log n)^3}{\varepsilon^2} \right)$ | Deterministic | $O(n^2\log\log n)$ |
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$.
Brute-force solution: Compute $d_c$ for every $c\in\mathcal C$
Idea 1:
- To get an optimum solution to point-separation: suffices to identify any object $c$ in an optimal solution, and compute $d_c$.
Idea 2:
- To get a +1 approximation: suffices to identify any object in 1-neighbourhood of an optimal solution.
- Similar principle applies for weaker approximations.
Idea 3:
- We can approximate $d_c$ for every object $c$, rather than compute it exactly.
Monte Carlo Algorithm
Recall Idea 1: 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.
If optimal $|C|=O(\sqrt{n})$, can find it 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
"Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane"
Jayson Lynch & Jack Spalding-Jamieson
Questions?