Dominating set of rectangles intersecting a straight line

Supantha Pandit ()
Additional contact information
Supantha Pandit: Dhirubhai Ambani Institute of Information and Communication Technology

Journal of Combinatorial Optimization, 2021, vol. 41, issue 2, No 9, 414-432

Abstract: Abstract The Minimum Dominating Set (MDS) problem is one of the well-studied problems in computer science. It is well-known that this problem is $$\mathsf {NP}$$ NP -hard for simple geometric objects; unit disks, axis-parallel unit squares, and axis-parallel rectangles to name a few. An interesting variation of the MDS problem with rectangles is when there exists a straight line that intersects each of the given rectangles. In the recent past researchers have studied the maximum independent set, minimum hitting set problems on this setting with different geometric objects. We study the MDS problem with axis-parallel rectangles, unit-height rectangles, and unit squares in the plane. These geometric objects are constrained to be intersected by a straight line. For axis-parallel rectangles, we prove that this problem is $$\mathsf {NP}$$ NP -hard. When the objects are axis-parallel unit squares, we present a polynomial time algorithm using dynamic programming. We provide a polynomial time algorithm for unit-height rectangles as well. For unit squares that touch the straight line at a single point from either side of the straight line, we show that there is an $$O(n\log n)$$ O ( n log n ) -time algorithm.

Keywords: Minimum dominating set; Straight line; Rectangles; Squares; $$\mathsf {NP}$$ NP -hard; Inclined line; Diagonal line; Touching a line; Intersecting a line (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00685-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:2:d:10.1007_s10878-020-00685-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00685-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().