Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane

Jayson Lynch, Jack Spalding-Jamieson

The (unweighted) point-separation problem asks, given a pair of points $s$ and $t$ in the plane, and a set of candidate geometric objects, for the minimum-size subset of objects wh…