Online Hitting Sets for Disks of Bounded Radii

In the geometric Hitting Set problem, we have $P\subseteq {ℝ}^d$ for some constant dimension $d$, and the sets in $𝒞$ are geometric objects of some type: for example, balls, unit balls, simplices, axis-aligned cubes, or hyper-rectangles. Depending on whether $P$ is finite or infinite, there are different versions of the problem. In this paper, we consider $P$ to be a finite set of points in ${ℝ}^2$.

When $P$ is finite, Even and Smorodinsky [12] initiated the study of the geometric online Hitting Set problem for various geometric objects. They established an optimal competitive ratio of $\mathrm{\Theta }(\log |P|)$ when the objects are intervals in $ℝ$, or half-planes or congruent disks in the plane. Later, Khan et al. [14] investigated this problem for a finite set of integer points $P\subseteq {[0,N)}^2\cap {\mathbb{Z}}^2$ and a collection $𝒞$ of axis-aligned squares $S\subseteq {[0,N)}^2$ with integer coordinates for $N>0$. They developed an $O(\log N)$-competitive algorithm for this variant. They also established a randomized lower bound of $\mathrm{\Omega }(\log |P|)$, where $P\subset {ℝ}^2$ consists of finitely many points and $𝒞$ consists of translates of an axis-aligned square. Recently, De et al. [6] considered the variant when $P$ is set of $n$ points in ${ℝ}^2$ and $𝒞$ consists of homothetic copies of a regular $k$-gon (for $k\ge 4$) with scaling factors in the interval $[1,M]$, and designed an $O(k^2\log M\log n)$-competitive randomized algorithm. Even though a disk can be approximated by a regular $k$-gon as $k\to \mathrm{\infty }$, this does not imply any competitive algorithm for disks with radii in the interval $[1,M]$.

We study the Online Hitting Set problem when $P$ is set of $n$ points in ${ℝ}^2$. Table 1 summarizes the existing results and the results of the current paper.

We now present our contributions and briefly discuss the technical ideas involved.

We present an $O(\log N)$-competitive deterministic algorithm for the geometric Online Hitting Set problem, where $P\subset {[0,N)}^2\cap {\mathbb{Z}}^2$, and $𝒞$ is a sequence of bottomless rectangles of the form $[a,b)\times [0,c)$ arriving one by one (Theorem 1 in Section 2). When a bottomless rectangle $[a,b)\times [0,c)$ arrives, our algorithm chooses hitting points guided by the canonical partition of the interval $[a,b]$ (see Section 2 for a definition). For each point $p$ in an offline optimum, this structured canonical partition ensures that $O(\log N)$ points are sufficient to hit all the incoming rectangles in ${[0,N]}^2\cap {\mathbb{Z}}^2$ that are hit by $p$. We prove that our algorithm is $O(\log N)$-competitive for a broader class of objects– sets $S\subset [a,b)\times ℝ$ with lowest-point property (see Section 2.2 for a definition).

Our main result is a deterministic $O(\log M\log n)$-competitive Online Hitting Set algorithm for an arbitrary set $P$ of $n$ points in the plane, and a sequence of disks of radii in the interval $[1,M]$ (Theorem 12 in Section 4). Previously, an $O(\log n)$-competitive algorithm was known only for congruent disks [12]. In particular, our result is the first $O(\log n)$-competitive algorithm that works for disks of radii in the interval $[1,1+\epsilon ]$ for any constant $\epsilon >0$ (Corollary 13).

However, a finite set of disks in the plane do not necessarily have the lowest-point property. We reduce the problem to objects with the lowest-point property in two steps. First, we consider a restricted version, the line-separated setting (Section 3), where the centers of disks in $𝒞$ lie on one side of a line (w.l.o.g., the $x$- or $y$-axis), while $P$ lies on the other side. We use the concept of disk hull for a point set (introduced by Dumitrescu et al. [10]), which generalizes the notion of convex hulls and $\alpha$-hulls. Among other important properties, the boundary of the disk hull is monotone w.r.t. the separating line. Using these properties, we reduce the Hitting Set problem in the line-separated setting to objects with the lowest-point property, and obtain an $O(\log n)$-competitive algorithm in the line-separated setting (Theorem 9 in Section 3).

In general, there is no restriction on the location of the points in $P$ and the centers of disks. We reduce the general problem to the line-separated setting as follows: We partition the disks of radii in the interval $[1,M]$ into $O(\log M)$ layers, ensuring that the ratio of radii of disks in each layer is bounded by at most 2. For each layer, our algorithm maintains a tiling of the plane into axis-aligned squares such that (a) any disk of a given layer contains the entire tile that contains the disk center, and (b) each disk intersects only $O(1)$ tiles. Our algorithm simultaneously runs several invocations of the line-separating algorithm (one for each directed grid line). When a disk arrives, our algorithm inserts it into all relevant invocations of the line-separating algorithms; we show that only $O(1)$ invocations are relevant. In the competitive analysis, we show that for each point $p$ in an offline optimum solution, our algorithm uses $O(\log n)$ hitting points for the disks in each layer that contain $p$. Since there are $O(\log M)$ layers, our algorithm is $O(\log M\log n)$-competitive.

We generalize our main result from disks to positive homothets of any convex body in the plane, where the radii in the interval $[1,M]$ are replaced by scaling factors in the interval $[1,M]$ (Theorem 14 in Section 5). Our online algorithm is based on a two-stage approach, similar to the case of disks, and it is $O(\log M\log n)$-competitive. The key technical difficulty arises from the geometric differences between a disk and a general convex body. It is easy to extend the concept of a disk hull to hulls for homothetic convex bodies. However, unlike for disks, the boundary of the hull is not necessarily $x$- or $y$-monotone: We show that it is monotone w.r.t. some carefully chosen directions. To generalize a layered decomposition of axis-parallel lines, we need two directions in which the hull is monotone, the two directions must be far apart (in the space of directions), to create a tiling with properties (a) and (b) above. We call a pair of directions satisfying these requirements a good pair of directions. We use a careful geometric argument, which heavily relies on convexity, a suitable affine transformation, and the variational method (i.e., the intermediate value theorem) to prove that every convex body in the plane admits a good pair of directions.

The unit disk hull of a point set was introduced by Dumitrescu et al. [10] as an analogue of the convex hull. Recall that the convex hull $\mathrm{conv}(P)$ of a point set $P\subset {ℝ}^2$ is the smallest convex set in the plane that contains $P$. Equivalently, it is the intersection of all closed half-planes that contain $P$; it can be computed by the classical “rotating calipers” algorithm, where we continuously rotate a line $\mathrm{\ell }$ around $P$ while $P$ remains in one closed half-plane bounded by $\mathrm{\ell }$. Intuitively, we obtain the unit disk hull of $P$ by rolling a unit disk, with center on or below the $x$-axis, around $P$. We generalize this notion to disks of any fixed radius $t>0$.

Dumitrescu et al. [10, Lemma 4] proved that $\partial {\mathrm{hull}}_t(P)$ is $x$-monotone²²2A curve in the plane is $x$-monotone if every vertical line intersects it at most once. for any $t>0$, and established other properties, which were used by Conroy and Tóth [4], as well.

Since we consider the case of disks with bounded radii, for our purposes, we need to compare two disk hulls for the same point set $P$ w.r.t. different radii; see Figure 4. We start with an easy observation.

(1) For every $i\in \{1,2\}$, the center of $C_i$ is below the $x$-axis, and so the leftmost and rightmost points of $C_1$ are also below the $x$-axis. The leftmost and rightmost points partition $C_i$ into two halfcircles, one above the center and one below the center. Both halfcircles are $x$-monotone: The lower halfcircle is convex curve and the upper halfcircle is concave. Since ${\gamma }_i$ lies entirely above the $x$-axis, it is contained in the upper halfcirlce, which is $x$-monotone and concave.
(2) The locus of centers of circles that contain both $p_1$ and $p_2$ is the orthogonal bisector of the line segment $p_1{p}_2$, that we denote by ${(p_1{p}_2)}^{⟂}$. Note that $p_1{p}_2$ is not vertical (or else ${(p_1{p}_2)}^{⟂}$ would be a horizontal line above the $x$-axis, and the centers of $C_1$ and $C_2$ would also be above the $x$-axis). As the center a circle containing $p_1$ and $p_2$ continuously moves from the center of $C_1$ down to $y=-\mathrm{\infty }$, the circular arc between $p_1$ and $p_2$ deforms continuously from ${\gamma }_1$ to the line segment $p_1{p}_2$. Since ${\gamma }_1$ concave, it lies above the segment $p_1{p}_2$. Since , the arc ${\gamma }_2$ lies between the arc ${\gamma }_1$ and the segment $p_1$ and $p_2$. Consequently, then ${\gamma }_2$ lies below ${\gamma }_1$, as claimed. $◀$

(1) Let $D\in {𝒟}_s$. Suppose, to the contrary, that the intersection $D\cap (\partial {\mathrm{hull}}_t(P))$ has two or more components. By Lemma 4(2), the $x$-coordinates of the components form disjoint intervals, and the components have a natural left-to-right ordering. Let $q_1$ be the rightmost point in the first component, and let $q_2$ be the leftmost point in the second component. Clearly $q_1,q_2\in \partial D$. Let $q^{\prime }$ be an arbitrary point in $\partial \text{hull}(A)$ between $q_1$ and $q_2$. Then $q^{\prime }$ lies on the boundary of some disk $D^{\prime }$ of radius $t$ whose center is below the $x$-axis, and whose interior is disjoint from $P$. In particular, neither $q_1$ nor $q_2$ is in the interior of $D^{\prime }$. Since the center of $D^{\prime }$ is below the $x$-axis, $\partial D^{\prime }$ contains two interior-disjoint circular arcs between $q$ and the $x$-axis; and both arcs must cross $\partial D$. We have found two intersection points $p_1,p_2\in \partial D\cap \partial D^{\prime }$ above the $x$-axis. Furthermore, between $p_1$ and $p_2$, the circular arc $\partial D$ lies above the circular arc $\partial D^{\prime }$, contradicting Lemma 5(2). This completes the proof of Property 1.
(2) Consider a point $p\in P$ that lies on the curve $\partial {\mathrm{hull}}_t(P)$ for some $t>0$. Then there exists a disk $D\in {𝒟}_t$ of radius $t$ centered at some point $c$ below the $x$-axis such that $p\in \partial D$. Let $c_1$ be the intersection point of the $x$-axis the line $cp$, and $c_2$ the orthogonal projection of $p$ to the $x$-axis. We describe two continuous motions, where the disk $D$ continuously changes while $p$ is in the circle $\partial D$ and there is no point in $P$ in the interior of $D$: First, a central dilation from center $p$ continuously moves $D$ to a disk $D_1$ centered at $c_1$. Second, the center of $D$ moves from $c_1$ towards $c_2$ continuously until its center reaches $c_2$ or a point $c_3$ where $\partial D$ contains both $p$ and another point $p^{\prime }\in P$. Let $r_p$ be radius of $D$ at that time. The continuous motion shows that $p\in \partial {\mathrm{hull}}_s(P)$ for all $s\in [r_p,t]$, but it is not in $\partial {\mathrm{hull}}_s(P)$ for all . $◀$

Note that Lemma 6(1) is not symmetric for : For a disk $D\in {𝒟}_t$ of radius $t$, the intersection $D\cap (\partial {\mathrm{hull}}_s(P))$ is not necessarily connected; see Figure 4 for an example.

We can reduce the Online Hitting Set problem for a finite set $P\subset {ℝ}^2$ and disks of bounded radii in the separated setting, to the Online Hitting Set problem for a finite subset of integer points and objects with the lowest-point property. We achieve the reduction in two steps:

1. (1)

   We choose a subset $Q\subseteq P$ of points that are relevant for a hitting set (Lemma 7); and

2. (2)

   we map the points in $P$ into a set of integer points $P^{\prime }\subset {[0,n]}^2\cap {\mathbb{Z}}^2$ (Lemma 8).

For a finite point set $P$ in the plane above the $x$-axis, let $Q=Q(P)$ be the set of points $p\in P$ such that $p\in \partial {\mathrm{hull}}_t(P)$ for some $t>0$.

Let $D$ be a disk of radius $t>0$ centered below the $x$-axis. By Lemma 4(4), $D\cap P$ contains a point in $\partial {\mathrm{hull}}_t(P)$. By the definition of $Q$, this point is in $Q$. $◀$

We may assume that the points in $P$ have distinct $x$-coordinates (if two or more points in $P$ have the same $x$-coordinate, w.l.o.g. a minimum hitting set would contain only the point with the smallest $y$-coordinate). Sort $P$ by increasing $x$-coordinates such that $P=\{p_0,\mathrm{\dots },p_{n-1}\}$. For every point $q\in Q$, let $t(q)>0$ be the maximum radius such that $q\in \partial {\mathrm{hull}}_{t(q)}(P)$. Consider the set of radii $T=\{t(q):q\in Q\}$. Sort the radii in $T$ in decreasing order as $t_0>t_1>\mathrm{\dots }>t_{|T|-1}$. We can now define the function $\pi :P\to {[0,n)}^2\cap {\mathbb{Z}}^2$. For every $p_i\in Q$, let $\pi (p_i)=(i,j)\text{ if and only if }t(p_i)=t_j$, that is, the first coordinate of $\pi (p_i)$ corresponds to the index $i$ of $p_i$ (the $x$-order of all points in $Q$), and the second coordinate of $\pi (p_i)$ corresponds to index $j$ of the radius $t_j=t(p_i)$. For every $p_i\in P\setminus Q$, let $\pi (p_i)=(i,|T|)$; see Figure 5 for an illustration. Finally, let $P^{\prime }=\pi (P)=\{\pi (p_i):p_i\in P\}$ and $Q^{\prime }=\pi (Q)=\{\pi (p_i):p_i\in Q\}$. Note that the points in $P^{\prime }\setminus Q^{\prime }$ lie above all points in $Q^{\prime }$. Since $\pi$ is injective, then it is a bijection between $P$ and $P^{\prime }$. Note also that $|T|\le |Q|\le |P|=n$, consequently $P^{\prime }\subset {[0,n]}^2\cap {\mathbb{Z}}^2$.

Let $D$ be a disk centered below the $x$-axis. We rephrase the lowest-point property in terms of $D\cap P$. Recall that the points in $P$ are sorted by $x$-coordinates. Suppose that $s=(s_x,s_y)$ is in $D\cap P$ and $s_x\in I\subset \mathrm{span}(D\cap P)$. Consider the point sets $P(I):=\{p=(p_x,p_y)\in D\cap P:p_x\in I\}$. By Lemma 7, we know that $D\cap Q\ne \mathrm{\varnothing }$; let $t$ be the largest radius in $T$ such that $Q(I)\cap \partial {\mathrm{hull}}_t(P)\ne \mathrm{\varnothing }$. We need to show that $D$ contains all points in $P(I)\cap \partial {\mathrm{hull}}_t(P)$.

Let $q_{\mathrm{left}}$ and $q_{\mathrm{right}}\in P(I)$, resp., be the leftmost and rightmost points in $P(I)\cap Q$; and let $L_{\mathrm{left}}$ and $L_{\mathrm{right}}$ be the vertical lines through $q_{\mathrm{left}}$ and $q_{\mathrm{right}}$. By the definition of $Q$, we have $q_{\mathrm{left}}\in \partial {\mathrm{hull}}_{t(q_{\mathrm{left}})}(P)$ and $q_{\mathrm{right}}\in \partial {\mathrm{hull}}_{t(q_{\mathrm{right}})}(P)$, and $t\ge \max \{t(q_{\mathrm{left}}),t(q_{\mathrm{right}})\}$ by the definition of $t$. Consequently, the intersection point $\mathrm{\ell }:=L_{\mathrm{left}}\cap \partial {\mathrm{hull}}_t(P)$ lies at or below $q_{\mathrm{left}}$, the intersection point $r:=L_{\mathrm{right}}\cap \partial {\mathrm{hull}}_t(P)$ lies at or below $q_{\mathrm{right}}$. Since $q_{\mathrm{left}},q_{\mathrm{right}}\in D$, then $D$ contains both $\mathrm{\ell }$ and $r$. We know that $\partial {\mathrm{hull}}_t(P)$ is an $x$-monotone curve by Lemma 4(2), and $D\cap \partial {\mathrm{hull}}_t(P)$ is connected by Lemma 6(2). Since $D$ contains both $\mathrm{\ell }$ and $r$, then $D$ contains the sub-curve of $\partial {\mathrm{hull}}_t(P)$ between $r$ and $\mathrm{\ell }$. Since all points in $P(I)$ are between the vertical lines $L_{\mathrm{left}}$ and $L_{\mathrm{right}}$, then $D$ contains all points in $P(I)\cap \partial {\mathrm{hull}}_t(P)$, as required. $◀$

We can now complete the reduction.

We are given a set $P\subset {ℝ}^2$ of $n$ points above the $x$-axis, and we receive a sequence $𝒞=(D_1,\mathrm{\dots },D_m)$ of disks centered on or below the $x$-axis in an online fashion. Let $\text{OPT}\subseteq P$ be a minimum hitting set for $𝒞$.

Initially, we compute the set $P^{\prime }\subset {[0,n]}^2\cap {\mathbb{Z}}^2$ as defined above Lemma 8. When a disk $D_i$ arrives, we compute the set $S_i=\pi (D_i\cap P)$, which has the lowest-point property by Lemma 8. The bijection $\pi$ maps OPT to a set ${\text{OPT}}^{\prime }=\pi (\text{OPT})\subseteq P^{\prime }$, where $|\text{OPT}|=|{\text{OPT}}^{\prime }|$. Here, ${\text{OPT}}^{\prime }$ is a hitting set for the sets ${𝒞}^{\prime }=(S_1,\mathrm{\dots },S_m)$.

We run the online algorithm ${\text{ALG}}_0$ described in Section 2.2 for the point set $P^{\prime }$ and the sequence ${𝒞}^{\prime }$ of sets. By Theorem 1, ALG returns a hitting set $H^{\prime }\subseteq P^{\prime }$ of size $|{\text{OPT}}^{\prime }|\cdot O(\log n)$. By Lemma 7, $H={\pi }^{-1}(H^{\prime })\subset P$ is a hitting set for $𝒞$, and its size is bounded by $|H|=|H^{\prime }|\le |{\text{OPT}}^{\prime }|\cdot O(\log n)=|\text{OPT}|\cdot O(\log n)$, as required. $◀$

We partition the disks of radii in the interval $[1,M)$ into $\lfloor \log M\rfloor +1$ layers as follows: for each $j\in \{0,1,\mathrm{\dots },\lfloor \log M\rfloor \}$, let layer $L_j$ be the set of disks of radii in the interval $[2^j,2^{j+1})$. The index of each layer $L_j$ is denoted by $j$.

For every $j\in \{0,1,\mathrm{\dots },\lfloor \log M\rfloor \}$, let ${\mathrm{\Lambda }}_j=\{{\alpha }_1{𝐯}_1+{\alpha }_2{𝐯}_2:({\alpha }_1,{\alpha }_2)$ $\in {\mathbb{Z}}^2\}$ be a two-dimensional lattice spanned by vectors ${𝐯}_1=2^{j-1/2}{𝐞}_1$ and ${𝐯}_2=2^{j-1/2}{𝐞}_2$, where ${𝐞}_1=(1,0)$ and ${𝐞}_2=(0,1)$ are the standard basis vectors. Let ${\tau }_j={[0,2^{j-1/2}]}^2$ be a square of side length $2^{j-1/2}$ with lower-left corner at the origin. Translates of ${\tau }_j$ (tiles), with translation vectors in the lattice ${\mathrm{\Lambda }}_j$, form the tiling ${𝒯}_j$. Let ${ℒ}_j$ denote the set of axis-parallel lines spanned by the sides of the tiles in ${𝒯}_j$.

We observe two key properties of the construction of layers and the tilings.

Since $\sigma \in L_j$, the radius of the disk $\sigma$ is in at least $2^j$. The tile $\tau$ is a translate of ${\tau }_j={[0,2^{j-1/2}]}^2$, and so its diameter is $\sqrt{2}\cdot 2^{j-1/2}=2^j$. If the center $c$ of $\sigma$ is in $S$, then every $p\in \tau$ is within distance $2^j$ from $c$, which implies that $\tau \subset \sigma$. $◀$

Let $D$ be a disk of radius $2^{j+2}$; see Figure 6. The orthogonal projection of $D$ to the $x$-axis (resp., $y$-axis) is an interval of length at most $2^{j+3}$. Since the distance between any two consecutive vertical (resp., horizontal) lines in ${ℒ}_j$ is $2^{j-1/2}$, then $D$ intersects at most $\lceil 2^{j+3}/2^{j-1/2}\rceil =\lceil 2^{7/2}\rceil =12$ horizontal and at most 12 vertical lines in ${ℒ}_j$. $◀$

For a directed line $L$, we denote by $L^{-}$ and $L^{+}$ the closed half-plane on the left and right of $L$, respectively. Given a directed line $L$ and the input $(P,𝒞$) of the Online Hitting Set problem, where $P$ is a set of points, and $𝒞$ is a sequence of disks in the plane, we define a subproblem $(P_L,{𝒞}_L)$ as follows: Let $P_L=P\cap L^{-}$, and let ${𝒞}_L$ be the subsequence of disks ${\sigma }_i\in 𝒞$ such that the center of ${\sigma }_i$ is in $L^{+}$ and ${\sigma }_i$ contains at least one point in $P_L$. Now for each subproblem $(P_L,{𝒞}_L)$, we can run the online algorithm ${\text{ALG}}_0$ described in Theorem 9, which was developed for the separated setting in Section 3. Let ${\text{ALG}}_0(L)$ denote the online algorithm, where we run the online algorithm ${\text{ALG}}_0$ on the subproblem $(P_L,{𝒞}_L)$.

We can now present our online algorithm ALG. In the current algorithm, we use the online algorithm ${\text{ALG}}_0(L)$ as a subroutine. For each $j\in \mathbb{N}\cup \{0\}$, let layer $L_j$ be the set of disks of radii in the interval $[2^j,2^{j+1})$. The algorithm maintains a hitting set $H\subseteq P$ for the disks presented so far. Upon the arrival of a new disk $\sigma$ with radius $r$, if it is already hit by a point in $H$, then do nothing. Otherwise, proceed as follows.

• $\mathrm{■}$

  First, find the layer $L_j$, where $j=\lfloor \log r\rfloor$, in which $\sigma$ belongs.

• $\mathrm{■}$

  Find the tile $\tau \in {𝒯}_j$ that contains the center of $\sigma$.

  • –

    If $P\cap \tau \ne \mathrm{\varnothing }$, then choose an arbitrary point $p\in P\cap \tau$ and add it to $H$.

  • –

    Otherwise, for every line $L\in {ℒ}_j$ that intersects $\sigma$, direct $L$ such that $L^{+}$ contains the center of $\sigma$, feed the disk $\sigma$ to the online algorithm ${\text{ALG}}_0(L)$, and add any new hitting point chosen by ${\text{ALG}}_0(L)$ to $H$.

We now prove that ALG is $O(\log M\log n)$-competitive.

Let $𝒞$ be a sequence of disks. For each $j\in \{0,1,\mathrm{\dots },\lfloor \log M\rfloor \}$, let ${𝒞}^j$ be the collection of disks in $𝒞$ with radii in the interval $[2^j,2^{j+1})$. Let $H$ and OPT, resp., be the hitting set returned by the online algorithm ALG and an (offline) minimum hitting set for $𝒞$. For every point $p\in \text{OPT}$, let ${𝒞}_p$ be the set of disks in $𝒞$ containing $p$. For each $j\in \{0,1,\mathrm{\dots },\lfloor \log M\rfloor \}$, let ${𝒞}_p^j$ be the set of disks in ${𝒞}^j$ containing $p$, i.e., ${𝒞}_p^j={𝒞}^j\cap {𝒞}_p$. Let $H_p^j\subseteq H$ be the set of points that ALG adds to $H$ in response to hit objects in ${𝒞}_p^j$. It is enough to show that for every $j\in \{0,1,\mathrm{\dots },\lfloor \log M\rfloor \}$ and $p\in \text{OPT}$, we have $|H_p^j|\le O(\log n)$.

Let $\tau$ be the tile in ${𝒯}_j$ that contains $p$, and let $𝒞_{}^{\prime }{}_p{}^j\subseteq {𝒞}_p^j$ be the subset of disks whose centers are located in $\tau$. To hit the first disk $\sigma \in 𝒞_{}^{\prime }{}_p{}^j$, our algorithm adds a point from $P\cap \tau$ to $H$. By Observation 10, any point in $P\cap \tau$ hits $\sigma$, as well as any subsequent disks in $𝒞_{}^{\prime }{}_p{}^j$. Our algorithm adds at most 1 point to $H$ to hit all the disks in $𝒞_{}^{\prime }{}_p{}^j$.