TY - GEN
T1 - Packing and covering with segments
AU - Mitchell, Joseph S.B.
AU - Pandit, Supantha
N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Dominating set
KW - Geometric set cover
KW - Inclined line
KW - NP-complete
KW - Piercing set
KW - Segments
UR - https://www.scopus.com/pages/publications/85080920361
U2 - 10.1007/978-3-030-39881-1_17
DO - 10.1007/978-3-030-39881-1_17
M3 - Conference contribution
SN - 9783030398804
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 198
EP - 210
BT - WALCOM
A2 - Rahman, M. Sohel
A2 - Sadakane, Kunihiko
A2 - Sung, Wing-Kin
PB - Springer
T2 - 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020
Y2 - 31 March 2020 through 2 April 2020
ER -