On the complexity of covering points by guillotine cuts

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

We show that the problem of covering a set of points in the plane with a minimum number of guillotine cuts is NP-complete. To that end, first we present a new NP-completeness proof…