Covering Weighted Points Using Unit Squares

For $k=2$, it takes $O((n/\epsilon )\log (1/\epsilon )+{(1/\epsilon )}^{O(1)})$ time. It begins by constructing a grid $G$ with cells of size $6/\epsilon$. For each cell $c$ of $G$, it first computes a $(1-\epsilon )$-approximate solution to $1\text{-Cover}(P_c)$, where $P_c$ denotes the set of points in $P$ contained in $c$. Among all cells in $G$, it greedily selects two cells whose $(1-\epsilon )$-approximate solution to $1\text{-Cover}(P_c)$ covers the maximum weight. To approximate $2$-Cover within each cell, it constructs an additional finer grid consisting of $O(1/{\epsilon }^3)$ horizontal and vertical lines, yielding $O(1/{\epsilon }^6)$ grid points. Each grid point is considered as a potential candidate for the upper-left corner of a square. Furthermore, this process is repeated over $O(1/\epsilon )$ different grids. Thus, the second term is $\mathrm{\Omega }(1/{\epsilon }^7)$ time.

Let $(s,s^{\prime })$ be an optimal pair of squares for $2$-Cover$(P)$. This pair corresponds to the point $q_{s,s^{\prime }}=(s_x,s_y,s_x^{\prime },s_y^{\prime })$ in the 4-dimensional parameter space. Let $P^{\prime }\subseteq P$ be the set of points covered by the union of $s$ and $s^{\prime }$, that is, $w(P^{\prime })=\text{opt}(P)$. By definition, we have $q_{s,s^{\prime }}\in H(p)$ for every $p\in P^{\prime }$. Thus, for each $p\in P^{\prime }$, there is at least one box in $B(p)$ that contains $q_{s,s^{\prime }}$, implying $\text{opt}(T)\ge \text{opt}(P)$.

Let $q_{r,r^{\prime }}=(r_x,r_y,r_x^{\prime },r_y^{\prime })$ be an optimal point for $\text{Depth}(T)$, and let $T^{\prime }\subseteq T$ be the set of boxes in $T$ that contain $q_{r,r^{\prime }}$. (By a symbolic perturbation to the boxes, we can avoid double counting while preserving the maximum depth.) Then the total weight of points $p\in P$ such that $q_{r,r^{\prime }}\in H(p)$ is exactly $\text{opt}(T)$. This means the pair of squares $(r,r^{\prime })$ together cover the total weight $\text{opt}(T)$ which is at most $\text{opt}(P)$. $◀$

As $|T|=O(n)$ and $\text{Depth}(T)$ can be solved in $O(n^{d/2})$ time [3], we have the following.

We note that Jin et al. [8] presented an algorithm that computes a $(1-\epsilon )$-approximate square for $1$-Cover$(P)$ in $O(n\log (1/\epsilon ))$ time. We adopt their grid-shifting technique for our problem. Let $G_3(a,b)$ denote the square grid with mesh size $3$, where the vertical and horizontal grid lines are defined as:

Consider the following nine grids: $G_3(a,b)$ for all $a,b\in \{1,2,3\}$. It can be easily shown that for any two unit squares $s_1$ and $s_2$, there exists at least one of these grids such that both $s_1$ and $s_2$ do not intersect any grid lines Therefore, for every grid $G\in \{G_3(a,b)\mid a,b\in \{1,2,3\}\}$, we aim to compute a pair of disjoint unit squares that do not intersect any grid lines of $G$, and we return the pair that covers the maximum total weight.

For a grid $G\in \{G_3(a,b)\mid a,b\in \{1,2,3\}\}$, we perform the following preprocessing. We compute a $(1-\epsilon )$-approximate square for $1\text{-Cover}(P_c)$ for every nonempty cell $c$ of $G$ where $P_c$ denotes the set of points of $P$ in $c$. We note that Jin et al. [8] give an algorithm, MaxCovCell$(c)$, which computes a $(1-\epsilon )$-approximate to $1\text{-Cover}(P_c)$ in $O(|P_c|\log (1/\epsilon )+1/{\epsilon }^2)$ time for a cell $c$ of $G$ if the size of $c$ is constant. For each cell of $G$ which contains larger than ${(1/\epsilon )}^2$ points, we run MaxCovCell. For the remaining nonempty cells, we run the exact algorithm which runs in $O(|P_c|\log |P_c|)$ time [2]. Let $n_1\ge \mathrm{\dots }{n}_j\ge (1/{\epsilon }^2)\ge n_{j+1}\ge \mathrm{\dots }\ge n_{j+k}$ be the sorted sequence of the number of points in nonempty cells of $G$. Then the total running time is ${\sum }_{i=1}^{j}O(n_i\log (1/\epsilon )+{(1/\epsilon )}^2)+{\sum }_{i=1}^{k}O(n_{i+j}\log (n_{i+j}))$, which is $O(n\log (1/\epsilon ))$.

To make use of the above results, we consider two cases based on whether there exists an optimal disjoint pair of squares for $2$-Cover$(P)$ such that the two squares are contained in different cells of $G$, or the two squares are contained in different cells of $G$.

We first consider the case where there exists an optimal pair of squares of type (1) for $2$-Cover$(P)$ such that the two squares are contained in different cells of $G$. In this case, there always exist at least two cells of $G$ whose respective $(1-\epsilon )$-approximate solutions together cover at least the weight of $\epsilon \cdot \text{opt}(P)$. Therefore, among all cells of $G$, we select the pair of cells whose $(1-\epsilon )$-approximate solutions together cover the maximum total weight. The union of these two $(1-\epsilon )$-approximate solutions then forms a $(1-\epsilon )$-approximate solution for $2$-Cover$(P)$.

Before moving onto the second case, we provide a summary of MaxCovCell(c).

For a given cell $c$, they form another (non-uniform) grid $G^{\prime }$ which consists of $O(1/\epsilon )$ horizontal lines and $O(1/\epsilon )$ vertical lines such that the following property holds: For a unit square $q$, it holds that $w(r(q)\cap c)\ge \epsilon \cdot w(q\cap c)$ where $r(q)$ denotes the largest axis-parallel rectangle contained in $q$ whose corners all lie on grid points of $G^{\prime }$. They construct such grid $G^{\prime }$ in $O(|P_c|\log (1/\epsilon ))$ time. The details of the method used to construct $G^{\prime }$ can be found in Lemmas 1 and 2 of [8].

For each cell $c^{\prime }$ of $G^{\prime }$, they calculate the sum of weights of points at the interior, edges, or corners of $c^{\prime }$ in $O(|P_c|\log (1/\epsilon ))$ time. Then they enumerate every vertex of $G^{\prime }$ and consider the unit square $q$ which has its top-left corner on the vertex. While enumerating those vertices and corresponding unit squares $q$, they calculate $w(r(q)\cap c)$. Then the one that covers the maximum weight can be found in $O(1/{\epsilon }^2)$ time with a standard incremental algorithm, and it is a $(1-\epsilon )$-approximate solution to $1\text{-Cover}(P_c)$.

Now we consider the case where an optimal pair of squares of type (1) for $2$-Cover$(P)$ is contained in the same cell of $G$. We can observe that once we compute a $(1-\epsilon )$-approximate pair of squares to $2\text{-Cover}(P_c)$ for every cell $c$ of $G$, and we can return the pair which covers the maximum total weight as a $(1-\epsilon )$-approximate solution to $2\text{-Cover}(P)$.

We first note that there exists an $O(n\log n)$-time exact algorithm for $2$-Cover(P) in the case where a disjoint optimal pair of squares exists [2]. For any cell $c$ with $|P_c|\le 1/{\epsilon }^2$, we can directly apply this algorithm for $2\text{-Cover}(P_c)$, which takes $O(|P_c|\log |P_c|)=O(|P_c|\log (1/\epsilon ))$ time. Therefore, we now focus on the remaining cells $c$ with $|P_c|>1/{\epsilon }^2$.

To compute a $(1-\epsilon )$-approximate solution of type (1) for $2\text{-Cover}(P_c)$, we further utilize the information obtained from the procedure MaxCovCell(c). Recall that we calculated $w(r(q)\cap c)$ for the squares $q$ which has its top-left corner on the vertex of $G^{\prime }$. Among the rectangle $r(q)$’s, we find a disjoint pair whose union covers the maximum total weight. This can be done using the observation that there always exists a horizontal or vertical line that separates the two disjoint squares. Without loss of generality, we can sweep a horizontal line across the plane and, at each position, track the maximum value of $w(r(q)\cap c)$ achievable by placing $q$ on one side of the sweep line. We repeat this process by sweeping the line in both directions. By combining the results from both sweeps, we can identify two disjoint rectangles among the $r(q)$’s whose union covers the maximum total weight. We note that this procedure can be implemented as part of the $MaxCovCell(c)$. Then a pair of unit squares, each containing one of the rectangles, is a $(1-\epsilon )$-approximate solution to $2\text{-Cover}(P_c)$.

Among all the cells $c$ of $G$, the pair of squares for $2\text{-Cover}(P_c)$ that covers the maximum total weight is a $(1-\epsilon )$-approximate solution to $2$-Cover(P).

For each grid $G\in \{G_3(a,b)\mid a,b\in \{1,2,3\}\}$, we compute a $(1-\epsilon )$-approximate solution for both cases in $O(n\log (1/\epsilon ))$ time and take the one that covers the larger total weight. Then we repeat this process for every grid $G\in \{G_3(a,b)\mid a,b\in \{1,2,3\}\}$, and we return the pair of squares that covers the maximum total weight. $◀$

If an optimal pair of squares for the type (1) case is an optimal pair of squares for $2$-Cover$(P)$, we can compute a $(1-\epsilon )$-approximate solution for $2$-Cover$(P)$ in $O(n\log (1/\epsilon ))$ time by Lemma 7. From now on, we assume that every optimal pair of squares for $2$-Cover$(P)$ intersect each other in their interior, and we focus on computing a $(1-\epsilon )$-approximate solution to the type (2) case. Once we obtain a $(1-\epsilon )$-approximate solution to the type (2) case, we compare it with the approximate solution to the type (1) case and return the one with the larger total weight.

Suppose that, for an optimal pair $(s_1,s_2)$ for $2$-Cover$(P)$, $s_2$ does not intersect $\text{int}(s^{\ast })$. See Figure 3(a). Since $s^{\ast }$ is an optimal square for $1$-Cover$(P)$, $w(s_1)\le w(s^{\ast })$. Thus, $w(s_1\cup s_2)\le w(s_1)+w(s_2)\le w(s^{\ast })+w(s_2)$, implying that $(s^{\ast },s_2)$ is an optimal pair of squares for $2$-Cover$(P)$. Observe that $\text{int}(s^{\ast })\cap \text{int}(s_2)=\mathrm{\varnothing }$, which contradicts our assumption that every optimal pair of squares for $2$-Cover$(P)$ intersect each other in their interiors. $◀$

Lemma 8 immediately implies the existence of an optimal pair of squares for $2$-Cover$(P)$ that are contained in the $3\times 3$ square centered at $s^{\ast }$. See Figure 3(b). We have a similar statement for a $(1-\epsilon )$-approximate square $\tilde{s}$ for $1$-Cover$(P)$.

Suppose that neither $s_1$ nor $s_2$ intersects $\text{int}(\tilde{s})$. Without loss of generality, assume that $w(s_1)\ge w(s_2)$. Then, $w(s_1)\ge (1-\epsilon )\text{opt}(P)/2$. Since $\tilde{s}$ is a $(1-\epsilon )$-approximate square for $1$-Cover$(P)$, $2w(\tilde{s})\ge (1-\epsilon )\text{opt}(P)$. Thus, $w(s_1\cup \tilde{s})=w(s_1)+w(\tilde{s})\ge (1-\epsilon )\text{opt}(P)$, implying that $(\tilde{s},s_1)$ is a $(1-\epsilon )$-approximate pair of squares for $2$-Cover$(P)$. $◀$

Recall that we compute a $(1-\epsilon )$-approximate solution to the type (2) case. By Lemma 9, we have the following.

By Lemmas 8, 9, and 10, the search space for $2$-Cover$(P)$ is a $5\times 5$ square centered at $s^{\ast }$ or $\tilde{s}$. We compute either $s^{\ast }$ or $\tilde{s}$ depending on the comparison between $n$ and $1/\epsilon$, identify the corresponding search space, and remove the points of $P$ lying outside this search space. Since $s^{\ast }$ can be computed in $O(n\log n)$ time [2] and $\tilde{s}$ can be computed in $O(n\log (1/\epsilon ))$ time by Lemma 7, this step can be completed in $O(n\log \min \{1/\epsilon ,n\})$ time.

From now on, we assume that every point of $P$ lies in the $5\times 5$ square. Clearly, there is a unit square that contains a subset of $P$ whose total weight is at least $w(P)/25$.

We construct a grid $𝒢$ with $O(1/\epsilon )$ horizontal and vertical lines with respect to $𝖰$ using the following lemma, which is obtained by combining Lemmas 1 and 2 of [8].

Let $V_{\text{Q}}$ denote the set of corners of the squares in Q. The weight of $v\in V_{\text{Q}}$ is set to the weight of its corresponding square. Let $L_v$ be the set of vertical lines obtained by applying Lemma 12 with $w_d=\epsilon \cdot w(P)/50$. Let $L_h$ be the set of horizontal lines defined in exactly the same way. Let $𝒢$ denote the grid formed by $L_v$ and $L_h$. By Lemma 12, $𝒢$ can be constructed in $O(n\log (\min \{n,1/\epsilon \}))$ time. In particular, when , we can simply draw horizontal and vertical lines through every point in $V_{\text{Q}}$.

For each square $q\in \text{Q}$, let $r(q)$ be the largest axis-parallel rectangle contained in $q$ whose corners all lie on grid points of $𝒢$. Let $\text{R}=\{r(q)\mid q\in \text{Q}\}$. The weight of $r(q)$ is set to the weight of $q$. If two or more squares in Q have the same rectangle snap-rounded in $𝒢$, R contains exactly one snap-rounded rectangle for those squares and the weight of the rectangle is set to the sum of the weights of those squares. See Figure 3(c). For a rectangle $r\in \text{R}$, we denote by $w(r)$ the weight of $r$. Let $\text{opt}(\text{R})$ and $\text{opt}(\text{Q})$ denote the total weights obtained by $2\text{-Depth}(\text{R})$ and $2\text{-Depth}(\text{Q})$, respectively.

For a point $p\in {ℝ}^2$, let $\text{Q}(p)=\{q\in \text{Q}\mid p\in q\}$. Note that there may exist squares $q\in \text{Q}(p)$ with $p\notin r(q)$. Let ${\text{Q}}^c(p)=\{q\in \text{Q}(p)\mid p\notin r(q)\}$.

Let $(p_1,p_2)$ be an optimal pair of points for $2\text{-Depth}(\text{Q})$. Assume that $p_1$ lies in the interior of a vertical slab ${\mathrm{\Gamma }}_v$ bounded by two consecutive lines in $L_v$. Also, assume that $p_1$ lies in the interior of a horizontal slab ${\mathrm{\Gamma }}_h$ bounded by two consecutive horizontal lines in $L_h$. Every square in ${\text{Q}}^c(p_1)$ must have at least two corners lying in $\text{int}({\mathrm{\Gamma }}_v)$ or at least two corners in $\text{int}({\mathrm{\Gamma }}_h)$. Since the total weight of the corners in $V_{\text{Q}}$ contained in $\text{int}({\mathrm{\Gamma }}_v)$ or $\text{int}({\mathrm{\Gamma }}_h)$ is at most $\epsilon \cdot w(P)/25$, $w({\text{Q}}^c(p_1))\le \epsilon \cdot w(P)/50$. Since $\text{opt}(P)=\text{opt}(\text{Q})\ge w(P)/25$ by Lemma 11, $w({\text{Q}}^c(p_1))\le \epsilon \cdot \text{opt}(\text{Q})/2$. The same argument applies to $p_2$, implying $w({\text{Q}}^c(p_2))\le \epsilon \cdot \text{opt}(\text{Q})/2$.

By defining $\text{R}(p)$ analogously to $\text{Q}(p)$, we have $w(\text{R}(p_1)\cup \text{R}(p_2))\ge w(\text{Q}(p_1)\cup \text{Q}(p_2))-w({\text{Q}}^c(p_1))-w({\text{Q}}^c(p_2))$. Since $w({\text{Q}}^c(p_1))+w({\text{Q}}^c(p_2))\le \epsilon \cdot \text{opt}(\text{Q})$ and $w(\text{Q}(p_1)\cup \text{Q}(p_2))=\text{opt}(\text{Q})$, we have $\text{opt}(\text{R})\ge (1-\epsilon )\cdot \text{opt}(\text{Q})$. $◀$

For a rectangle $r=[x_1,x_2]\times [y_1,y_2]$, let $x(r)=[x_1,x_2]$ and let $y(r)=[y_1,y_2]$. Let ${ℐ}_x=\{x(r)\mid r\in \text{R}\}$ and ${ℐ}_y=\{y(r)\mid r\in \text{R}\}$.

Let $q$ and $q^{\prime }$ be the squares in $𝖰$ with $x(r(q))=I$ and $x(r(q^{\prime }))=I^{\prime }$. Let $x(q)=[a_1,a_2]$ and $x(q^{\prime })=[a_1^{\prime },a_2^{\prime }]$. Since , and $q,q^{\prime }$ are unit squares, we have , and thus . This implies that $x_2\le x_2^{\prime }$ by the snap rounding method. The same can be shown for the other cases analogously. $◀$ By Lemma 14, we obtain the following corollary. Note that $\text{R}\subseteq \{\alpha \times \beta \mid \alpha \in {ℐ}_x,\beta \in {ℐ}_y\}$.

Recall that $𝒢$ can be constructed in $O(n\log \min \{n,1/\epsilon \})$ time. After sorting the grid lines, we can use binary search to snap round every square in Q in $O(n\log \min \{n,1/\epsilon \})$ total time.

Let ${\text{Q}}_1\subset \text{R}$ be the set of rectangles hit by $p_1$. Let ${\text{Q}}_2\subset \text{R}$ be the set of rectangles hit by $p_2$ but not by $p_1$. Note that $w({\text{Q}}_1)+w({\text{Q}}_2)=\text{opt}(i,j)$ as ${\text{Q}}_1\cap {\text{Q}}_2=\mathrm{\varnothing }$.

Let $\gamma =\max \{r_y\mid r\in ({\text{Q}}_2\cap {\text{R}}_{i,j})\}$. See Figure 4(a). Observe that . We will prove that $w({\text{Q}}_1)=\text{Depth}({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$ and $w({\text{Q}}_2)=\text{Depth}({\text{R}}_{j\setminus i}\cup {\text{R}}_{i,j}^c(\gamma ))$.

Every rectangle $r\in {\text{Q}}_1$ has $y(p_1)\le r_y$ by the definition. Every rectangle in ${\text{Q}}_1$ is from either ${\text{R}}_{i\setminus j}$ or ${\text{R}}_{i,j}$. (Note that ${\text{R}}_{i\setminus j}$ and ${\text{R}}_{i,j}$ are disjoint.) For a rectangle of the latter case, that is $r\in {\text{Q}}_1\cap {\text{R}}_{i,j}$, observe that $r\in {\text{R}}_{i,j}(\gamma )$ as we have . Therefore ${\text{Q}}_1\subset ({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$.

Every rectangle in ${\text{Q}}_2$ is from either ${\text{R}}_{j\setminus i}$ or ${\text{R}}_{i,j}$. (Note that ${\text{R}}_{j\setminus i}$ and ${\text{R}}_{i,j}$ are disjoint.) For a rectangle of the latter case, that is $r\in {\text{Q}}_2\cap {\text{R}}_{i,j}$, observe that $r_y\le \gamma$ by the definition of $\gamma$. Therefore such $r$ is contained in ${\text{R}}_{i,j}^c(\gamma )$. Therefore ${\text{Q}}_2\subset ({\text{R}}_{j\setminus i}\cup {\text{R}}_{i,j}^c(\gamma ))$.

Now we first show that $w({\text{Q}}_1)=\text{Depth}({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$. As ${\text{Q}}_1\subset ({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$, it is clear that $w({\text{Q}}_1)\le \text{Depth}({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$. Now suppose . As every rectangle in $({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$ intersects $\text{int}({\mathrm{\Gamma }}_i)$, there always exists an optimal point $p^{\prime }$ for $\text{Depth}({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$ such that $p^{\prime }\in {\mathrm{\Gamma }}_i$. Let ${\text{R}}^{\prime }$ be the set of rectangles in $({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$ hit by $p^{\prime }$, that is $w({\text{R}}^{\prime })=\text{Depth}({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$. Observe that ${\text{R}}^{\prime }\cap {\text{Q}}_2=\mathrm{\varnothing }$ because we have ${\text{R}}^{\prime }\subset ({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))$, ${\text{Q}}_2\subset ({\text{R}}_{j\setminus i}\cup {\text{R}}_{i,j}^c(\gamma ))$, and $({\text{R}}_{i\setminus j}\cup {\text{R}}_{i,j}(\gamma ))\cap ({\text{R}}_{j\setminus i}\cup {\text{R}}_{i,j}^c(\gamma ))=\mathrm{\varnothing }$. Then the total weight of rectangles in R hit by a new pair $(p^{\prime },p_2)$ is $w({\text{R}}^{\prime })+w({\text{Q}}_2)>w({\text{Q}}_1)+w({\text{Q}}_2)$, which contradicts that $(p_1,p_2)$ is an optimal pair of points for $2\text{-Depth}(i,j)$.

In a similar way, we can show that $w({\text{Q}}_2)=\text{Depth}({\text{R}}_{j\setminus i}\cup {\text{R}}_{i,j}^c(\gamma ))$. $◀$