On the complexity of covering points by disjoint segments and by guillotine cuts

Authors: Delia Garijo, Alberto Márquez, Rodrigo I. Silveira

We show that two geometric cover problems in the plane, related to covering points with disjoint line segments, are NP-complete. Given $n$ points in the plane and a value $k$, the first problem asks if all points can be covered by $k$ disjoint line segments; the second problem treats the analogous question for $k$ guillotine cuts.