Online Hitting Set for Axis-Aligned Squares

We present the key ideas for axis-aligned squares (of arbitrary size), since all technical tools readily generalize to axis-aligned rectangles of bounded aspect ratio. Recall that the point set $P\subset {ℝ}^2$ is given in advance, that axis-aligned squares $𝒞=\{S_1,S_2\mathrm{\dots }\}$ arrive one-by-one, and that we need to construct a hitting set $H\subset P$ of size $|H|\le O(|\text{OPT}|\log n)$ where $\text{OPT}\subset P$ is an optimal hitting set for $𝒞$. Each square $S_i\in 𝒞$ is hit by an unknown point $p\in \text{OPT}$ in the offline optimum; we would like to add points to $H$ that also hit many other potential squares that contain (the unknown) point $p$. Our general strategy is to preprocess $P$ into a hierarchy of depth $O(\log n)$, and then use this hierarchy to narrow down the possible location of the points in OPT. In one dimension, where $P\subset ℝ$ and $𝒞$ is a sequence of intervals, a simple binary hierarchy is sufficient [23].

In the plane, we preprocess $P\subset {ℝ}^2$ with the classical BBD tree data structure by Arya et al. [5], which has found a wide range of applications in computational geometry, including binary space partitions, range searching, and many other problems [1, 4, 5, 11, 25]; this data structure was previously used for the online geometric set cover problem by Khan et al. [26]. For a set $P\subset {ℝ}^2$ of $n$ points, the BBD tree is a hierarchical space partition of depth $O(\log n)$, where all cells of the partition are “fat” (in the sense defined below). When a square $S_i$ arrives online, we choose hitting points via a top-down traversal of the BBD tree. Specifically, we “activate” the $O(1)$ lowest inactive cells of the BBD tree that intersect $S_i$ (see Section 4 for details), and add $O(1)$ extremal points in each of these cells to $H$. The extremal points of a rectangular cell $C$ are simply the leftmost, rightmost, topmost, and bottommost points in $P\cap C$ (i.e., extremal with respect to axis-parallel directions). Extremal points have previously been used in computational geometry for many different problems, including guarding set or shortest path problems [8, 10, 16, 30], as well as restricted versions of the online hitting set problem in combination with quadtrees [26].

Unfortunately, the cells in the BBD tree are not necessarily convex – they include rectangles with a rectangular hole – so we need to define extremal points much more carefully. The intersection $C_v\cap S_i$ of a cell $C_v$ of the BBD tree and a square $S_i$ can be reduced to axis-aligned half-spaces, and we show that $C_v\cap S_i\cap P$ is either empty or contains at least one extremal point of $C_v$ (see Section 3.2 for details). Note that these techniques work for arbitrary axis-aligned fat rectangles (the fatness of a rectangle is quantified by the aspect ratio $\varrho$): extremal points in the four axis-parallel directions are sufficient if $S_i$ is an axis-aligned rectangle, and the intersection $C_v\cap S_i$ reduces to halfplanes if both $C_v$ and $S_i$ are fat.

Each (unknown) point $p\in \text{OPT}$ is contained in $O(\log n)$ cells of the BBD tree. After $O(\log n)$ steps, in which a square $S_i$ arrives that contains the point $p\in \text{OPT}$ but our algorithm adds $O(1)$ new points to $H$, the BBD tree is “saturated”, in the sense that all cells containing $p$ are activated – at this point, the extremal points in $H$ already hit any subsequent square $S_i$ that contains $p$. We prove that our algorithm uses only $O(\log n)$ points for any sequence of squares that can be optimally hit by a single point; see Section 4.2 for further details.

Consider the online geometric set cover problem: given a set $𝒮$ of $n$ geometric objects in ${ℝ}^d$, and a sequence of points arriving one by one, we need to maintain a set cover $C_i\subset 𝒮$ for the first $i$ points in an online fashion. Note, however, that the hitting set and the set cover problems are not equivalent in the geometric setting: points in the plane form a 2-parameter family (parameterized by $x$- and $y$-coordinates), while axis-aligned squares form a 3-parameter family (parameterized by, e.g., a lower-left corner and a side length). In the online hitting set problem, the 2-parameter family is known in advance, and the 3-parameter family arrives without prior knowledge – the roles are reversed in online set cover. That is, an online hitting set algorithm makes decisions based on less information (i.e., more uncertainty) than an analogous online set cover algorithm. Importantly, these problems are not equivalent, and techniques developed for one problem do not easily carry over to the other. Khan et al. [26] studied a restricted version of the online set cover problem for axis-aligned squares. In their model, both a collection $𝒮$ of $m$ axis-aligned squares and a set $\tilde{P}$ of $n$ points are given in advance. Points from $\tilde{P}$ arrive online, and we need to maintain a set of squares $C_i\subset 𝒮$ that cover the first $i$ points. Using a BBD tree decomposition over the point set $\tilde{P}$, they obtain a deterministic $O(\log n)$-competitive algorithm.

We remark that their result yields an $O(\log m)$-competitive algorithm for the unrestricted version of the online set cover problem for axis-aligned squares (where $\tilde{P}$ is not given in advance). An arrangement of $m$ squares in the plane determines $O(m^2)$ cells: points in the same cell are contained in the same subset of squares (they are combinatorially indistinguishable). We can define $\tilde{P}$ as a set of $O(m^2)$ representative points, one from each cell. When a sequence of arbitrary points $p_1,p_2,\mathrm{\dots }$ arrive online, we can replace each point $p_i$ with the representative of its cell, and invoke the algorithm by Khan et al. [26], with competitive ratio $O(\log |\tilde{P}|)=O(\log m^2)=O(\log m)$.

Section 2 begins by introducing the necessary definitions and then reviews a classical space partition data structure, the Balanced Box Decomposition Tree (BBD tree) [6]. Section 3 presents several key properties of BBD trees. Section 4 describes our online algorithm for hitting axis-aligned rectangles, and analyzes its competitive ratio. Next, Section 5 generalizes the main result from axis-aligned squares to positive homothets of an arbitrary polygon. Finally, Section 6 concludes with a discussion of future research directions.

Let $T$ be a BBD tree, and let $U\subset V(T)$ be a set of nodes that corresponds to a family of interior-disjoint cells crossed by $R$. Let $v\in U$. Recall that a cell of the BBD tree is defined as $C_v=r_{\mathrm{out}}(v)\setminus r_{\mathrm{in}}(v)$, where $r_{\mathrm{in}}(v)$ may be empty. Depending on how $R$ intersects with $C_v$, we distinguish between two cases.

Assume w.l.o.g. that $R$ intersects two vertical edges of $r_{\mathrm{out}}(v)$ (i.e., $R$ crosses $r_{\mathrm{out}}(v)$ horizontally); see Figure 2(a). Since the aspect ratios of $R$ and $r_{\mathrm{out}}$ are $\varrho$ and at most 3, respectively, then we have

In particular, this implies . Note also that $0pt(R\cap r_{\mathrm{out}}(v))=0pt(r_{\mathrm{out}}(v))$. If $R$ horizontally crosses $k$ interior-disjoint rectangles $r_{\mathrm{out}}(v_1),\mathrm{\dots },r_{\mathrm{out}}(v_k)$, then

hence $k\le 3\varrho$. That is, $R$ horizontally crosses at most $3\varrho$ interior-disjoint cells. Similarly, $R$ may cross at most $3\varrho$ cells vertically. However, if $R$ crosses a cell $C_v$ horizontally and another cell $C_w$ vertically, then $\mathrm{int}(C_v)\cap \mathrm{int}(C_w)\ne \mathrm{\varnothing }$. In particular, $U$ cannot contain both $v$ and $w$. Overall, $R$ crosses at most $3\varrho$ interior-disjoint cells in this case.

Assume w.l.o.g. that $R$ intersects the left side of both $r_{\mathrm{in}}(v)$ and $r_{\mathrm{out}}(v)$; see Figure 2(b). Let ${\mathrm{dist}}_{\mathrm{left}}(v)$ denote the distance between the left sides of $r_{\mathrm{in}}$ and $r_{\mathrm{out}}$. Then we have $0pt(R\cap C_v)={\mathrm{dist}}_{\mathrm{left}}(v)$, and in particular . Due to the stickiness, we also have $0pt(r_{\mathrm{in}})\le {\mathrm{dist}}_{\mathrm{left}}(v)$. Overall, we obtain

By the pigeonhole principle, $R$ crosses at most $3\varrho$ interior-disjoint cells between the left sides of $r_{\mathrm{in}}$ and $r_{\mathrm{out}}$. Similarly, $R$ crosses at most $3\varrho$ interior-disjoint cells between the right (respectively, top, bottom) sides of $r_{\mathrm{in}}$ and $r_{\mathrm{out}}$. As a result, $R$ crosses $O(\varrho )$ interior-disjoint cells in this case. $◀$

We state a few properties of extremal points that will be used in the competitive analysis of our online algorithm in Section 4. Let $P$ be a finite set of points in a bounding box (a square), and $T$ be a BBD tree for $P$.

Assume w.l.o.g. that $L$ is the vertical line $x=a$, for some $a\in ℝ$, and let $L^{-}=\{(x,y)\in {ℝ}^2:x\le a\}$ be the left half-plane; see Figure 4(a). We prove the contrapositive. If $\mathrm{ext}(r)\cap L^{-}=\mathrm{\varnothing }$, then every point $p=(p_x,p_y)\in \mathrm{ext}(P)$ satisfies $p_x>a$. In particular, we have $p_x>a$ for the leftmost point in $P\cap r$, hence we have $p_x>a$ for all points in $P\cap r$. This implies that $P\cap r\cap L^{-}=\mathrm{\varnothing }$, as required. $◀$

Assume w.l.o.g. that $L$ is the vertical line $x=a$ for some $a\in ℝ$, and let $L^{-}=\{(x,y)\in {ℝ}^2:x\le a\}$; see Figure 4(b) for an illustration. We prove the contrapositive. Suppose that ${\mathrm{Ext}}_v\cap L^{-}=\mathrm{\varnothing }$. Then every point of ${\mathrm{Ext}}_v$ has $x$-coordinate larger than $a$. Recall that $C_v={\bigcup }_{i=1}^k{r}_i$. The leftmost point of $P\cap C_v$ is the leftmost point of $P\cap r_i$ for some $1\le i\le k$. This point is included in $\mathrm{ext}(r_i)$, and hence in ${\mathrm{Ext}}_v={\bigcup }_{i=1}^k\mathrm{ext}(r_i)$. Consequently, ${\mathrm{Ext}}_v$ contains the leftmost point of $P\cap C_v$. Then, all points of $P\cap C_v$ have $x$-coordinate larger than $a$. Hence, we have $P\cap C_v\cap L^{-}=\mathrm{\varnothing }$, as required. $◀$

Assume w.l.o.g. that $L_1$ and $L_2$ are the vertical lines $x=a$ and $x=b$, respectively, for some $a,b\in ℝ$; see Figure 5 for an illustration. Let $L_1^{-}=\{(x,y)\in {ℝ}^2:x\le a\}$ be the left half-plane. If $L_2^{+}$ is also a left half-plane, then $L_1^{-}\cap L_2^{+}$ is a half-plane and Lemma 5 completes the proof. So we may assume that $L_2^{+}=\{(x,y)\in {ℝ}^2:x\ge b\}$ is the right half-plane, and (since $S=L_1^{-}\cap L_2^{+}\ne \mathrm{\varnothing }$).

Assume that $S$ contains a corner $c=(c_1,c_2)$ of $r_{\mathrm{in}}(v)$. Recall that $C_v$ is subdivided along the lines spanned by the sides of $r_{\mathrm{in}}(v)$. One of the subdivision lines is $x=c_1$, where (since $c\in S$). Consequently, every subrectangle of $C_v$ intersects at most one of $L_1$ and $L_2$.

Since $P\cap C_v\cap S\ne \mathrm{\varnothing }$, there exists a point $p\in P\cap C_v\cap S$. Assume that $p\in r_x$, where $r_x$ is one of the subrectangles of $C_v$. Since $\mathrm{ext}(r_x)\cap S\subseteq {\mathrm{Ext}}_v\cap S$ and by Lemma 4, we have $\mathrm{ext}(r_x)\cap S\ne \mathrm{\varnothing }$, thus we have ${\mathrm{Ext}}_v\cap S\ne \mathrm{\varnothing }$. Hence, the lemma follows. $◀$

Assume w.l.o.g. that $L_1$ is the vertical line $x=a$, and $L_2$ is the horizontal line $y=b$ for some $a,b\in ℝ$; see Figure 6 for an illustration. Let $L_1^{-}=\{(x,y)\in {ℝ}^2:x\le a\}$ be the left half-plane and $L_2^{+}=\{(x,y)\in {ℝ}^2:y\ge b\}$ be the top half-plane; see Figure 6. Since $L_1\cap L_2=(a,b)\in r_{\mathrm{in}}(v)$, then $L_1$ intersects the subrectangles of $C_v$ above and below $r_{\mathrm{in}}$(v); and $L_2$ intersects the subrectangles of $C_v$ to the left and right of $r_{\mathrm{in}}(v)$. In particular, none of the subrectangles in $C_v$ intersects both $L_1$ and $L_2$.

Since $P\cap C_v\cap S\ne \mathrm{\varnothing }$, there exists a point $p\in P\cap C_v\cap S$. Assume that $p\in r_x$, where $r_x$ is one of the subrectangles of $C_v$. Since $r_x$ intersects at most one of $L_1$ and $L_2$, then $r_x\cap S$ equals $r_x\cap L_1^{-}$ or $r_x\cap L_2^{+}$. In both cases, by Lemma 4, we have $\mathrm{ext}(r_x)\cap S\ne \mathrm{\varnothing }$. Now $\mathrm{ext}(r_x)\subseteq {\mathrm{Ext}}_v$ implies that ${\mathrm{Ext}}_v\cap S\ne \mathrm{\varnothing }$, as required. $◀$

The algorithm activates the root in step $i=1$. In the remainder of the proof, we may assume that $i>1$ and the root is already active. Before the arrival of $S_i$, we have $p\notin H_{i-1}$, so the leaf node of the BBD tree that contains $p$ is inactive. Let $v$ be the lowest active node in the BBD tree such that $C_v$ contains $p$. Let $u$ and $w$ be the two children of $v$ such that $p\in C_u$ (hence $p\notin C_w$).

We need to show that the algorithm activates $u$ in step $i$. Suppose, for the sake of contradiction, that $u$ is inactive at the beginning of step $i$. Then its sibling $w$ is also inactive at that time (since our algorithm always activates two siblings).

The algorithm activates the highest inactive nodes that contain any of the four corners of $S_i$ (and their siblings), as well as the highest inactive nodes corresponding to every cell crossed by $S_i$ (and their siblings). Therefore, we may assume that neither $C_u$ nor $C_w$ contains any corner of $S_i$, and neither of them is crossed by $S_i$. Since $C_v=C_u\cup C_w$, then $C_v$ does not contain any corner of $S_i$, either. If $S_i$ crosses $C_v$, then at the beginning of step $i$, node $v$ is active but its children $u$ and $w$ are inactive, and so the algorithm would activate both $u$ and $w$ in step $i$. For this reason, we may also assume that $S_i$ does not cross $C_v$.

We examine all possible positions of $C_v$ and $C_u$ relative to $S_i$. Recall that $C_v=r_{\mathrm{out}}(v)\setminus r_{\mathrm{in}}(v)$, where $r_{\mathrm{in}}(v)$ may be empty.

In this case, all four corners of $S_i$ are in $r_{\mathrm{out}}(v)$. If all four corners of $S_i$ are in $r_{\mathrm{in}}(v)$, then $p\in S_i\subset r_{\mathrm{in}}(v)$, which contradicts the assumption that $p\in C_v$. Therefore, a corner of $S_i$ lies in $r_{\mathrm{out}}(v)\setminus r_{\mathrm{in}}(v)=C_v$. For this corner of $S_i$, the highest inactive node is $u$ or $w$. Consequently, the algorithm activates both siblings $u$ and $w$. In particular, $u$ is activated.

Since $C_v$ does not contain any corners of $S_i$, then all corners of $S_i$ in $r_{\mathrm{out}}(v)$ are in $r_{\mathrm{in}}(v)$. Since $S_i\not\subset r_{\mathrm{out}}(v)$, then $r_{\mathrm{in}}(v)$ contains either one or two corners of $S_i$. We examine each case separately:

Assume w.l.o.g. that $r_{\mathrm{in}}(v)$ contains the lower-right corner of $S_i$ (as in Figure 7(b)). Denote by $a$ the lower-right corner of $S_i$. Then $S_i$ also contains precisely one corner of $r_{\mathrm{in}}(v)$, namely its upper-left corner. Since the remaining three corners of $S_i$ are outside of both $r_{\mathrm{in}}(v)$ and $C_v$, they are outside of $r_{\mathrm{out}}(v)$. Consequently, $S_i$ also contains precisely one corner of $r_{\mathrm{out}}(v)$, namely the upper-left corner of $r_{\mathrm{out}}(v)$. Since $p\in S_i\cap C_v$, then Lemma 7 yields ${\mathrm{Ext}}_v\cap S_i\ne \mathrm{\varnothing }$. However, $C_v$ was activated in a previous step. This implies that ${\mathrm{Ext}}_v\subset H_{i-1}$, hence $S_i\cap H_{i-1}\ne \mathrm{\varnothing }$: a contradiction.

Recall that an axis-aligned rectangle $S_i$ crosses a cell $C_v$, for $v\in V(T)$ if $C_v\cap S_i\ne \mathrm{\varnothing }$ but $C_v$ does not contain any vertex of $S_i$ and $S_i$ does not contain any vertex of $C_v$. Consequently, $S_i$ crosses $C_v$: a contradiction.

Let $ab$ be an edge of $S_i$ that intersects $C_v$, where $a$ and $b$ are corners of $S_i$. Since $r_{\mathrm{out}}(v)$ contains neither $a$ nor $b$, then both $a$ and $b$ are outside of $r_{\mathrm{out}}(v)$, and so the two edges of $S_i$ orthogonal to $ab$ are also outside of $r_{\mathrm{out}}(v)$. Consequently, $r_{\mathrm{out}}(v)$ intersects one edge of $S_i$ or two parallel edges of $S_i$.

Assume w.l.o.g. that $r_{\mathrm{out}}(v)$ intersects the right edge $ab$ of $S_i$; see Figure 7(d). Let $L$ be the vertical line spanned by $ab$, and let $L^{-}$ be the left half-plane determined by $L$. Note that $p\in S_i\cap C_v$ implies $p\in L^{-}$, so $P\cap C_v\cap L^{-}\ne \mathrm{\varnothing }$. Lemma 5 yields ${\mathrm{Ext}}_v\cap S_i\ne \mathrm{\varnothing }$. However, $C_v$ was activated in a previous step. This implies that ${\mathrm{Ext}}_v\subset H_{i-1}$, hence $S_i\cap H_{i-1}\ne \mathrm{\varnothing }$: a contradiction.

Assume w.l.o.g. that $r_{\mathrm{out}}(v)$ intersects the left and right edges of $S_i$. If $S_i$ does not contain any corners of $r_{\mathrm{in}}(v)$, then $S_i$ does not contain any vertex of $C_v$, and so $S_i$ crosses $C_v$: a contradiction.

So we may assume that $S_i$ contains some corners of $r_{\mathrm{in}}(v)$. Lemma 6 yields ${\mathrm{Ext}}_v\cap S_i\ne \mathrm{\varnothing }$. However, $C_v$ was activated in a previous step. This implies that ${\mathrm{Ext}}_v\subset H_{i-1}$, hence $S_i\cap H_{i-1}\ne \mathrm{\varnothing }$: a contradiction.

Since $p\in P\cap C_v$, then $P\cap C_v\ne \mathrm{\varnothing }$, and so ${\mathrm{Ext}}_v\ne \mathrm{\varnothing }$. Since $C_v$ is active, then ${\mathrm{Ext}}_v\subset H_{i-1}$, and $C_v\subset r_{\mathrm{out}}(v)\subset S_i$ implies that ${\mathrm{Ext}}_v\subset S_i$. Consequently, $H_{i-1}\cap S_i\ne \mathrm{\varnothing }$: a contradiction. $◀$

Let ${\widehat{𝒞}}_p\subseteq {𝒞}_p$ be the set of rectangles $S_i\in {𝒞}_p$ for which the algorithm adds new hitting points to $H_i$ (that is, any rectangle $S_i\in {𝒞}_p\setminus {\widehat{𝒞}}_p$ contains $p$, but does not require new hitting points as $S_i\cap H_{i-1}\ne \mathrm{\varnothing }$). By Lemma 9, the algorithm activates a cell containing $p$ to hit each rectangle in ${\widehat{𝒞}}_p$. In the BBD tree, the cells containing $p$ correspond to a descending path from root to leaf. Since the depth of the BBD tree for $n$ points is $O(\log n)$, there are $O(\log n)$ such cells, which implies that $|{\widehat{𝒞}}_p|\le O(\log n)$, as required. $◀$ This completes the proof of Theorem 8. Now we have all the tools to prove Theorem 1.

Theorem 8 implies the claim if $1\le \varrho \le 2$. Assume that $\varrho >2$. Partition the incoming rectangles into $O(1+\log \varrho )$ classes: let ${ℛ}_0$ be the set of rectangles of aspect ratio in $[1,2]$, and for $j=1,\mathrm{\dots },\lceil {\log }_2\varrho \rceil$, let ${ℛ}_j$ be the set of rectangles of aspect ratio in $(2^j,2^{j+1}]$. Within each class, we further separate rectangles whose width is at least their height from those whose height exceeds their width, yielding $2(1+\lceil {\log }_2\varrho \rceil )$ classes in total. Applying the linear transformation $(x,y)\mapsto (x/2^j,y)$ (respectively, $(x,y)\mapsto (x,y/2^j)$) to both $P$ and the rectangles in the $j$-th class maps each rectangle to one with aspect ratio in $[1,2]$. Since the scaling is applied to both $P$ and the rectangles, any hitting set for the original instance corresponds to a hitting set of the same size in the scaled instance. Furthermore, the size of an offline optimum for each class is at most $|\mathrm{OPT}|$, the size of the offline hitting set of all rectangles. Running a separate instance of our online algorithm with $\varrho =2$ on each of the $O(\log \varrho )$ classes yields a hitting set of size $O(|\mathrm{OPT}|\cdot \log n)$ per class. Taking the union of the resulting hitting sets over all classes is a hitting set of size $O(|\mathrm{OPT}|\cdot (1+\log \varrho )\log n)$. $◀$