On some geometric optimization problems with segments

We study three fundamental geometric optimization problems – INDEPENDENT SET, PIERCING SET, and DOMINATING SET – on sets of axis-parallel segments in the plane. We consider special cases in which the segments are either unit length or are anchored on an inclined line (a line with slope −1). When the segments are anchored on both sides, we prove that all three problems are NP-complete²; NP-completeness was known for the corresponding problems with axis-parallel rectangles anchored on an inclined line (Correa et al., 2015 [1], Mudgal and Pandit, 2015 [2], Pandit, 2017, [3]). Further, we prove that the DOMINATING SET problem with unit segments in the plane is NP-complete. When the input segments are anchored on one side of the inclined line, known polynomial-time algorithms can be used to solve the INDEPENDENT SET and PIERCING SET problems. We also discuss approximation and the discrete variants of some of the problems.