Advertisement
Published in:
2020 | OriginalPaper | Chapter
Packing and Covering with Segments
Authors : Joseph S. B. Mitchell, Supantha Pandit
Published in: WALCOM: Algorithms and Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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 they 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 (Throughout, we refer to NP-completeness of problems, as the decision versions of the NP-hard optimization problems we consider are all readily seen to be in NP.); NP-completeness was known for the corresponding problems with axis-parallel rectangles anchored on an inclined line (Correa et al. [4], Mudgal and Pandit [9], Pandit [10]). 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, there are polynomial-time algorithms for the independent set and piercing set problems.