2 papers
cs.CG2026
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 and in the plane, and a set of candidate geometric objects, for the minimum-size subset of objects wh…
cs.DM2025
Slant/Gokigen Naname is NP-complete, and Some Variations are in P
Jayson Lynch, Jack Spalding-Jamieson
In this paper we show that a generalized version of the Nikoli puzzle Slant is NP-complete. We also give polynomial time algorithms for versions of the puzzle where some constraint…