Separating Colored Points with Minimum Number of Rectangles

2021/07/21 by Assadian, Navid, Shanjani, Sima Hajiaghaei, Zarei, Alireza
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2107.09821

Abstract

In this paper we study the following problem: Given k disjoint sets of points, P₁, …, P_k on the plane, find a minimum cardinality set T of arbitrary rectangles such that each rectangle contains points of just one set P_i but not the others. We prove the NP-hardness of this problem.

Related

• On Separating Points by Lines
• On Triangular Separation of Bichromatic Point Sets
• Maximum Area Rectangle Separating Red and Blue Points
• Point Set Isolation Using Unit Disks is NP-complete
• Red-Blue Point Separation for Points on a Circle