In a minimum p union problem (MinpU), given a hypergraph \(G=(V,E)\) and an integer p, the goal is to find a set of p hyperedges \(E'\subseteq E\) such that the number of vertices covered by \(E'\) (that is \(|\bigcup _{e\in E'}e|\) ) is minimized. It was known that MinpU is at least as hard as the densest k-subgraph problem. A question is: how about the problem in some geometric settings? In this paper, we consider the unit square MinpU problem (MinpU-US) in which V is a set of points on the plane, and each hyperedge of E consists of a set of points in a unit square, the goal of the MinpU-US problem is to select p squares such that the number of points covered by the union of these p squares is as small as possible. A \((\frac{1}{1+\varepsilon },4)\) -bicriteria approximation algorithm is presented, that is, the algorithm finds at least \(\frac{p}{1+\varepsilon }\) unit squares covering at most \(4\,opt\) points, where opt is the optimal value for the MinpU-US instance (the minimum number of points that can be covered by p unit squares).
