Talks and Poster Presentations (with Proceedings-Entry):
S. Bhore, S. Pandit, S. Roy:
"Balanced Covering Problem in Bicolored point Sets";
- 2019-03-20; in: "Proceeding of EuroCG 2019",
We study a variation of the classical set cover problem called the balanced covering (BC) problem
on a set of red and blue points in the Euclidean plane. Let P be a set of red and blue points in
the plane. An object is called a balanced object with respect to P, if it contains an equal number
of red and blue points from P. In the BC problem, the objective is to cover the points in P
with a minimum number of homogeneous geometric objects (i.e., unit squares, intervals) such
that each object is balanced. For points in the plane, we prove that the BC problem is NP-hard
when the covering objects are unit squares. For points on a line, we show that if the ratio of the
total numbers of reds and blues is more than 2 then, there exists no solution of the BC problem.
Subsequently, we devise a linear time exact algorithm for the BC problem with intervals. Finally,
we study the study the problem of computing a balanced object of maximum cardinality. For
this, we give polynomial time algorithms with unit squares in the plane and intervals on a line.
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.