Abstract
For a given shape S in the plane, one can ask what is the lowest possible density of a point set P that pierces (“intersects”, “hits”) all translates of S. This is equivalent to determining the covering density of S and as such is well studied. Here we study the analogous question for families of shapes where the connection to covering no longer exists. That is, we require that a single point set P simultaneously pierces each translate of each shape from some family \(\mathcal F\). We denote the lowest possible density of such an \(\mathcal F\)-piercing point set by \(\pi _T(\mathcal F)\). Specifically, we focus on families \(\mathcal F\) consisting of axis-parallel rectangles. When \(|\mathcal F|=2\) we exactly solve the case when one rectangle is more squarish than \(2\times 1\), and give bounds (within \(10\%\) of each other) for the remaining case when one rectangle is wide and the other one is tall. When \(|\mathcal F|\ge 2\) we present a linear-time constant-factor approximation algorithm for computing \(\pi _T(\mathcal F)\) (with ratio 1.895).
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
In a game of Battleship, the opponent secretly places ships of a fixed shape on an \(n\times n\) board and your goal is to sink them by identifying all the cells the ships occupy (the ships are stationary). Consider now the following puzzle: If the opponent placed a single \(2\times 3\) ship, how many attempts do you need to surely hit the ship at least once? The answer depends on an extra assumption. If you know that the ship is placed, e.g., vertically, it is fairly easy to see that the answer is roughly \(n^2/6\): When n is a multiple of 6, then one hit is needed per each of the \(n^2/6\) interior-disjoint translates of the \(2\times 3\) rectangle that tile the board and, on the other hand, a lattice with basis [2, 0], [0, 3] achieves the objective. The starting point of this paper was to answer the question when it is not known whether the ship is placed vertically or horizontally. It turns out that the answer is \(n^2/5+\mathcal O(n)\) hits (the main term comes from Theorem 1 (ii) whereas the \(\mathcal O(n)\) correction term is due to the boundary effect).
Motivated by the above puzzle, we study the following problem: Given a family \(\mathcal F\) of compact shapes in the plane, what is its translative piercing density \(\pi _T(\mathcal F)\), that is, the lowest density of a point set that pierces (“intersects”, “hits”) every translate of each member of the family? Here the density of an infinite point set P (over the plane) is defined in the standard fashion as a limit of its density over a disk \(D_r\) of radius r, as r tends to infinity. The piercing density \(\pi _T(\mathcal F)\) of the family is then defined as the infimum over all point sets that pierce every translate of each member of the family [5, Ch. 1], [15]. (See Sect. 1.1 for precise definitions.) Note that unlike in the puzzle, we allow translations of each shape in the family by any, not necessarily integer, vector.
First, we cover the case when the family \(\mathcal F=\{S\}\) consists of a single shape. The problem is then equivalent to the classical problem of determining the translative covering density \(\vartheta _T(S)\) of the shape S: Indeed, determining the translative covering density \(\vartheta _T(S)\) amounts to finding a (sparsest possible) point set P such that the translates \(\{p+S\mid p\in P\}\) cover the plane, that is,
(Here “+” is the Minkowski sum.) This is the same as requiring that
that is, the point set P pierces all translates of the shape \(-S\). Hence \(\vartheta _T(S)=\pi _T(\{-S\})=\pi _T(\{S\})\). Specifically, when S tiles the plane, then the answer is simply \(\pi _T(\{S\})=1/{\text {Area}}(S)\), where \({\text {Area}}(S)\) is the area of S. We note that apart from the cases when S tiles the plane, the translative covering density \(\vartheta _T(S)\) is known only for a few special shapes S such as a disk or a regular n-gon [5, Ch. 1].
For the rest of this work (apart from the Conclusions) we limit ourselves to the case when \(\mathcal F\) consists of \(n\ge 2\) axis-parallel rectangles. First we consider the special case \(n=2\) (Theorem 1 in Sect. 2), then we consider the case of arbitrary \(n\ge 2\) (Theorem 2 in Sect. 3).
Related Work. There is a rich literature on related (but fundamentally different) fronts dealing with piercing finite collections. One broad direction is devoted to establishing combinatorial bounds on the piercing number as a function of other parameters of the collection, most notably the matching number [2, 10, 11, 13, 17, 20, 23, 24, 26,27,28,29] or in relation to Helly’s theorem [12, 21, 23]; see also the survey articles [14, 24]. Another broad direction deals with the problem of piercing a given set of shapes in the plane (for instance axis-parallel rectangles) by the minimum number of points and concentrates on devising algorithmic solutions, ideally exact but frequently approximate; see for instance [7,8,9]. Indeed, the problem of computing the piercing number corresponds to the hitting set problem in a combinatorial setting [19] and is known to be NP-hard even for the special case of axis-aligned unit squares [18]. The theory of \(\varepsilon \)-nets for planar point sets and axis-parallel rectangular ranges is yet another domain at the interface between algorithms and combinatorics in this area [3, 32].
A third direction that appears to be most closely related to this paper is around the problem of estimating the area of the largest empty axis-parallel rectangle amidst n points in the unit square, namely, the quantity A(n) defined below. Given a set S of n points in the unit square \(U=[0,1]^2\), a rectangle \(R \subset U\) is empty if it contains no points of S in its interior. Let A(S) be the maximum volume of an empty box contained in U (also known as the dispersion of S), and let A(n) be the minimum value of A(S) over all sets S of n points in U. It is known that \(1.504 \le \lim _{n \rightarrow \infty } n A(n) \le 1.895\); see also [1, 30, 34, 36]. The lower bound is a recent result of Bukh and Chao [6] and the upper bound is another recent result of Kritzinger and Wiart [31]. It is worth noting that the upper bound \(\varphi ^4/(\varphi ^2+1)=1.8945\ldots \) can be expressed in terms of the golden ratio \(\varphi =\frac{1}{2}(1+\sqrt{5})\). The connection will be evident in Sect. 3.
1.1 Preliminaries
Throughout this paper, a shape is a Lebesque-measurable compact subset of the plane. Given a shape S, let \({\text {Area}}(S)\) denote its area. We identify points in the plane with the corresponding vectors from the origin. Given two shapes \(A,B\subset \mathbb {R}^2\), we denote by \(A+B = \{ a+b \mid a\in A, b\in B \}\) their Minkowski sum. A translate of a shape S by a point (vector) p is the shape \(p+S = \{ p+s \mid s\in S \}\).
In the next three definitions we introduce the (translative) piercing density \(\pi _T(\mathcal F)\) of a family \(\mathcal F\) of shapes in the plane. Then we define a certain shorthand notation for the special case when \(\mathcal F\) consists of two axis-parallel rectangles.
Definition 1
(\(\mathcal F\)-piercing sets). Given a family \(\mathcal F\) of shapes in the plane, we say that a point set P is \(\mathcal F\)-piercing if it intersects all translates of all the shapes in \(\mathcal F\), that is, if
Definition 2 (Density of a point set)
Given a point set P and a bounded domain D with area \({\text {Area}}(D)\), we define the density of P over D by \(\delta (P,D)=\frac{|P\cap D|}{{\text {Area}}(D)}\).
Given a (possibly infinite and unbounded) point set P, we define its asymptotic upper and lower densities by
where \(D_r\) is the disk with radius r centered at the origin.
Definition 3
(Translative piercing density \(\pi _T(\mathcal F)\)). Fix a family \(\mathcal F\) of shapes in the plane. Then we define the (translative) piercing density by
and the (translative) lattice piercing density \(\pi _L(\mathcal F)\) by
Pairs of Axis-Parallel Rectangles. Let \(R_{w\times h}\) denote a rectangle with width w and height h. Here we introduce a shorthand notation for the case when \(\mathcal F=\{R_{a\times b},R_{c\times d}\}\) consists of two axis-parallel rectangles. If \(a\le c\) and \(b\le d\) then clearly \(\pi _T(\mathcal F)=\pi _L(\mathcal F)=1/(ac)\) as the lattice with basis \(\{[a,0],[0,c]\}\) that pierces all translates of the smaller rectangle also pierces all translates of the larger rectangle. Otherwise we can suppose \(a\ge c\) and \(b\le d\). Stretching horizontally by a factor of c and then vertically by a factor of b, we have
and likewise for \(\pi _L(\mathcal F)\). Thus it suffices to determine
for \(w,h\ge 1\). We say that a point set (resp. a lattice) P is (w, h)-piercing if it is \(\{R_{w\times 1},R_{1\times h}\}\)-piercing. It is sometimes convenient to work with the reciprocals \(A_T(w,h)=1/\pi _T(w,h)\) (resp. \(A_L(w,h)=1/\pi _L(w,h)\)) which correspond to the largest possible per-point area of a (w, h)-piercing point set (resp. lattice). Note that \(A_L(w,h)\le A_T(w,h)\), since the sparsest (w, h)-piercing point set perhaps does not have to be a lattice. Also, \( A_T(w,h)\le \min (w,h)\) as translates of the smaller rectangle tile the plane and each translate has to be pierced.
1.2 Results
The following theorem and its corollary summarize our results for piercing all translates of two axis-parallel rectangles in \(\mathbb {R}^2\).
Theorem 1
Fix \(w,h\ge 1\).
-
(i) When \(\lfloor w\rfloor \ne \lfloor h\rfloor \) then \(A_T(w,h)=A_L(w,h)=\min \{w,h\}\).
-
(ii) When \(\lfloor w\rfloor = \lfloor h\rfloor =k\ge 1\), set \(w=k+x\), \(h=k+y\) for \(x,y\in [0,1)\). Then
$$ \max \left\{ k, k+ xy - \frac{k-1}{k}(1-x)(1-y)\right\} \le A_L(w,h)\le A_T(w,h) \le k+xy. $$
Note that the inequalities in (ii) become equalities in two different cases: When \(k=1\) then \(A_L(w,h)=A_T(w,h)=k+xy\) and when \(\min \{x,y\}=0\) (that is, when w or h is an integer) then \(A_L(w,h)=A_T(w,h)=\min \{w,h\}=k\).
Corollary 1
Given a family \(\mathcal F=\{R_1,R_2\}\) consisting of two axis-parallel rectangles, a 1.086-approximation of \(\pi _T(\mathcal F)\) can be computed in \(\mathcal O(1)\) time. The output piercing set is a lattice with density at most \((\frac{5}{2}-\sqrt{2})\cdot \pi _T(\mathcal F)\).
We then address the general case of piercing all translates of any finite collection of axis-parallel rectangles.
Theorem 2
Given a family \(\mathcal F=\{R_1,\dots ,R_n\}\) consisting of n axis-parallel rectangles, a 1.895-approximation of \(\pi _T(\mathcal F)\) can be computed in \(\mathcal O(n)\) time. The output piercing set is a lattice with density at most \((1+\frac{2}{5}\sqrt{5})\cdot \pi _T(\mathcal F)\).
2 Piercing Two Rectangles
Proof
(of Theorem 1). (i) Note that \(A_T(w,h) \le \min \{w,h\}\): Indeed, any (w, h)-piercing point set has to pierce all the translates of the rectangle with smaller area and certain copies of that smaller rectangle tile the plane. To complete the proof, it suffices to exhibit a suitable (w, h)-piercing lattice. Without loss of generality suppose that \(\lfloor h\rfloor < \lfloor w\rfloor \). We will show that the lattice \(\varLambda _1\) with basis \(u_1=[1,h-1]\), \(v_1=[1,-1]\) (see Fig. 1(a)) is (w, h)-piercing. Note that the area of the fundamental parallelogram of the lattice is \((h-1)+1=h\), as required.
We first show that \(\varLambda _1\) pierces all \(1 \times h\) rectangles. Observe that the \(1 \times h\) rectangles centered at points in \(\varLambda _1\) tile the plane. Denote this tiling by \(\mathcal T\). Let now R be any \(1 \times h\) rectangle. Its center is contained in one of the rectangles in \(\mathcal T\), say \(\sigma \). Then the center of \(\sigma \) pierces R, as required.
We next show that \(\varLambda _1\) pierces all \(w \times 1\) rectangles. It suffices to show that \(\varLambda _1\) pierces all \(w_0 \times 1\) rectangles, where \(w_0=\lfloor h\rfloor +1\). Let R be any \(w_0 \times 1\) rectangle. Assume that R is not pierced by \(\varLambda _1\). Translate R downwards until it hits a point in \(\varLambda _1\), say q, and then leftwards until it hits another point in \(\varLambda _1\), say p. Let \(R'\) denote the resulting rectangle. Then p is the top left corner of \(R'\). Observe that the top and the right side of \(R'\) are not incident to any other point in \(\varLambda _1\). Consider the lattice point \(s:=p+u_1+(w_0-1)v_1\); note that \(x(s)-x(p)=w_0\) and \(y(s)-y(p)=h-1-\lfloor h\rfloor \in [-1,0)\). As such, s is contained in the right side of \(R'\), a contradiction. It follows that R is pierced by \(\varLambda _1\), as required.
(ii) In order to prove the lower bound it suffices to exhibit suitable lattices. We will show that the following lattices do the job: The lattice \(\varLambda _2\) with basis \(u_2=[1,k-1]\), \(v_2=[1,-1]\) (see Fig. 1(b)) attests that \(A_T(k+x,k+y)\ge k\). Note that the area of the fundamental parallelogram of \(\varLambda _2\) is \((k-1)+1=k\), as required. The lattice \(\varLambda _3\) with basis \(u_3=[1,h-1]\), \(v_3=[(w-1)/k,-1]\) (see Fig. 1(c)) attests that \(A_T(k+x,k+y)\ge k+ xy - \frac{k-1}{k}(1-x)(1-y)\). Note that the area of the fundamental parallelogram of \(\varLambda _3\) is \((w-1)(h-1)/k +1= (k+ xy) - \frac{k-1}{k}(1-x)(1-y)\), as required.
For both lattices, the proof proceeds by contradiction as in part (i). Assume that there exists an unpierced rectangle of dimensions either \(w\times 1\) or \(1\times h\). Translate the rectangle downwards until it hits a point in the lattice, say q, and then leftwards until it hits another point in the lattice, say p. For \(\varLambda _2\), note that \(r:=p+u_2\) lies on the right edge of the \(1\times h\) rectangle and that \(s:=p+u_2+(k-1)v_2\) lies on the top edge of the \(w\times 1\) rectangle. Similarly, for \(\varLambda _3\) note that \(r:=p+u_3\) is the top right corner of the \(1\times h\) rectangle and that \(s:=p+u_3+ k v_3\) lies on the right edge of the \(w\times 1\) rectangle. Either way, we get a contradiction.
Finally, we show the upper bound, that is, \(A_T(w,h)\le k+xy\). Recall that \(A_T(w,h) \le \min \{w,h\}=k + \min \{x,y\}\); we will obtain an improved bound \(A_T(w,h)\le k+xy\) by an integral calculus argument (which originates from a probabilistic argument). Let P be a (w, h)-piercing point set, where \(w=k+x\), \(h=k+y\) with \(k\in \mathbb {N}\) and \(x,y\in [0,1)\). The desired upper bound on \(A_T(w,h)\) will follow from a lower bound on the density \( \delta (P,D_r) = \frac{|P \cap D_r|}{{\text {Area}}(D_r)}\), where \(D_r\) is the disk with radius r centered at the origin. Fix a radius r and write \(P_r = P \cap D_r\).
Given a point \(a=(a_x,a_y)\in \mathbb {R}^2\), we denote by \(R_a=[a_x-w,a_x]\times [a_y-h,a_y]\) the \(w\times h\) rectangle whose top right corner is a. For brevity, we denote \(R=R_{(w,h)}=[0,w]\times [0,h]\). We consider two sets of \(w\times h\) rectangles: Those that intersect \(D_r\) and those that are contained within \(D_r\). We denote the sets of their top right corners by \(X=\{a\in \mathbb {R}^2\mid R_a\cap D_r\ne \emptyset \}\) and \(W=\{a\in \mathbb {R}^2\mid R_a\subset D_r\}\), respectively. See Fig. 2(a).
Given a rectangle \(R_a\), we define its zone \(Z_a\) to be a union of \(k^2\) closed rectangles with sizes \((1-x)\times (1-y)\) each, arranged as in Fig. 2(b). Note that \({\text {Area}}(Z_a)=k^2(1-x)(1-y)\). Further, let \(I_a:=|P_r \cap Z_a|\) and \(J_a:=|P_r \cap (R_a \setminus Z_a)|\) be the number of points of \(P_r\) contained in \(R_a\) inside its zone and outside of it, respectively. We make two claims about \(I_a\) and \(J_a\).
Claim 1
If \(a\in W\) then \((k+1)I_a+ kJ_a \ge k(k+1)\).
Proof
Fix \(a\in W\). Since \(R_a\subset D_r\), we have \(P\cap R_a=P_r\cap R_a\). The key observation is that for any point \(p \in R_a \setminus Z_a\), the set \(R_a \setminus \{p\}\) contains k pairwise disjoint rectangles of dimensions either all \(w\times 1\) or all \(1\times h\). We thus must have \(|P_r \cap R_a |\ge k+1\), except when \(P_r \cap R_a \subseteq Z_a\), in which case we must have \(| P_r\cap R_a| \ge k\).
Denote \(I=I_a\) and \(J=J_a\). There are two simple cases:
-
1.
\(J \ge 1\): Then \(I+J \ge k+1\), thus \((k+1)I+ kJ \ge kI+kJ \ge k(k+1)\).
-
2.
\(J=0\): Then \(I \ge k\), thus \((k+1)I+ kJ \ge k(k+1)\). \(\square \)
Claim 2
We have
Proof
Fix \(p\in P_r\). Note that the set \(X_p=\{a\in \mathbb {R}^2\mid p\in Z_a\}\) of top right corners of \(w\times h\) rectangles whose zone contains p is a subset of X congruent to Z. Thus \({\text {Area}}(X_p)={\text {Area}}(Z)\). Summing over \(p\in P_r\) we obtain
For \(J_a\) we proceed completely analogously. \(\square \)
Now we put the two claims together to get a lower bound on \(|P_r|\).
Claim 3
We have \( |P_r| \ge \frac{{\text {Area}}(W)}{k+xy}.\)
Proof
First, applying Claim 1 to all \(w\times h\) rectangles \(R_a\) with \(a\in W\) and then invoking \(W\subset X\), we obtain
By Claim 2 and straightforward algebra we further rewrite this as
where the last equality follows from
The bound \(|P_r| \ge \frac{{\text {Area}}(W)}{k+xy}\) follows by rearranging. \(\square \)
Consequently, by Claim 3 we have
where we used that \({\text {Area}}(W) / {\text {Area}}(D_r)\rightarrow 1\) as \(r\rightarrow \infty \). This in turn gives
and completes the proof of Theorem 1. \(\square \)
For a visual illustration of our results, see Fig. 3.
Proof
(of Corollary 1). It suffices to show that
A computer algebra system (such as Mathematica) shows that the supremum is attained when \(k=2\) and when x, y are both equal to a value that makes the two expressions inside the \(\max \{\}\) operator equal. This happens for \(x=y=\sqrt{2}-1\) and the corresponding value is \((5-2\sqrt{2})/2 <1.086\) as claimed. \(\square \)
3 Piercing n Rectangles
In this section we prove Theorem 2. Let \(\varphi =\frac{1}{2}(1+\sqrt{5})\) be the golden ratio. In Lemma 2 we show that a lattice \(\varLambda _\varphi \) with basis \(u=[1,\varphi ], v=[\varphi ,-1]\) pierces all rectangles with area \(\varphi ^4\) or larger, irrespective of their aspect ratio. See Fig. 4 (a). Theorem 2 then follows easily by rescaling \(\varLambda _\varphi \) to match the smallest-area rectangle from the family.
Recall the well-known sequence of Fibonacci numbers defined by the following recurrence:
The first few terms in the sequence are listed in Table 1 for easy reference; here it is convenient to extend this sequence by \(F_{-1}=1\) and \(F_0=0\).
We first list several properties of Fibonacci numbers.
Lemma 1
The following identities hold for every integer \(m \ge 1\):
-
1.
\(F_m \varphi + F_{m-1} = \varphi ^m\),
-
2.
\(F_m \varphi - F_{m+1} = (-1)^{m+1} \varphi ^{-m}\),
-
3.
\(F_{2m+1}F_{2m-1} - (F_{2m})^2 =1\).
Proof
This is straightforward to verify, for instance using the well-known formula \(F_m=\frac{1}{\sqrt{5}}(\varphi ^m-\psi ^m)\), where \(\psi =-1/\varphi \). \(\square \)
Next we prove a lemma that establishes a key property of the lattice \(\varLambda _\varphi \).
Lemma 2
The area of every empty rectangle amidst the points in \(\varLambda _\varphi \) is at most \(\varphi ^4\).
Proof
Let R be a maximal axis-parallel empty rectangle, bounded by four lattice points p, q, r, s from the left, below, right and top, respectively. Refer to Fig. 4 (b). Then pqrs is a fundamental parallelogram of the lattice; as such, its area is \(\varphi ^2+1\). Clearly, we may assume \(p=(0,0)\). Further, we may assume \(q=cu+dv\), \(s=au +bv\), where a, b, c, d are nonnegative integers: Indeed, since \(\varLambda _\varphi \) is invariant under rotation by \(90^\circ \), we can assume that the width of R is at least as large as its height. Points q, s thus lie on the “funnel” (depicted in Fig. 4 (a) dotted) within the angle formed by the vectors u, v. The coordinates of points s, q, r and the area of the parallelogram pqrs are:
Since s lies above the horizontal line through p and since q lies below it, we have \(a \varphi -b>0\) and \(c \varphi -d <0\). This implies \(a,b,c,d>0\) and rewrites as \(\frac{b}{a}<\varphi <\frac{d}{c}\), so in particular \(ad>bc\). Together with the expression for \({\text {Area}}(pqrs)=\varphi ^2+1\) this yields \(|ad-bc|=ad-bc=1\). To summarize, we have
The relation \(ad-bc=1\) implies that \(\gcd (a,b)=\gcd (c,d)=1\). By a result from the theory of continued fractions [33, 22, Ch. 10], relation (2) implies that the fractions b/a and d/c are consecutive convergents of \(\varphi \). Moreover, it is well known that the convergents of \(\varphi \) are ratios of consecutive Fibonacci numbers:
Thus we can assume that \(\frac{b}{a}= \frac{F_{2k}}{F_{2k-1}}\). There are two cases:
Case 1: \(\frac{d}{c}= \frac{F_{2k-1}}{F_{2k-2}}\), and thus \(\frac{F_{2k}}{F_{2k-1}}< \varphi < \frac{F_{2k-1}}{F_{2k-2}}\).
Case 2: \(\frac{d}{c}= \frac{F_{2k+1}}{F_{2k}}\), and thus \(\frac{F_{2k}}{F_{2k-1}}< \varphi < \frac{F_{2k+1}}{F_{2k}}\).
(Note that in both cases we indeed have \(ad-bc=1\) by Lemma 1, Item 3.) We compute \({\text {Area}}(R)\) using Items 1 to 2 of Lemma 1. Let \(\varDelta {x}\) and \(\varDelta {y}\) denote the side-lengths of R.
Case 1: We have
thus \({\text {Area}}(R) = \varDelta {x} \cdot \varDelta {y} = \varphi ^{2k+1} \varphi ^{-(2k-3)} = \varphi ^4\), as required.
Case 2: Similarly, we have
thus \({\text {Area}}(R) = \varDelta {x} \cdot \varDelta {y} = \varphi ^{2k+2} \varphi ^{-(2k-2)} = \varphi ^4\), as required. \(\square \)
With Lemma 2 at hand, the proof of Theorem 2 is straightforward.
Proof
(of Theorem 2). Let \(R\in \mathcal F\) be the smallest-area rectangle among those in \(\mathcal F\). By Lemma 2, the lattice \(\varLambda _\varphi \) pierces all axis-parallel rectangles with area at least \(\varphi ^4\). Thus the rescaled lattice \( \varLambda _\varphi '=\sqrt{{\text {Area}}(R)/\varphi ^4}\cdot \varLambda _\varphi \) pierces all axis-parallel rectangles with area at least \({\text {Area}}(R)\). In particular, it pierces all rectangles in \(\mathcal F\). Since the fundamental parallelogram of \(\varLambda _\varphi \) has area \(\varphi ^2+1\), the fundamental parallelogram of \(\varLambda _\varphi '\) has area \((\varphi ^2+1)/\varphi ^4\cdot {\text {Area}}(R)\) and gives an approximation factor \(\varphi ^4/(\varphi ^2+1) =1+\frac{2}{5}\sqrt{5}<1.895\) as claimed. Note that computing the smallest-area rectangle and the rescaling only take \(\mathcal O(n)\) time. \(\square \)
Remarks. We have learned from the recent article of Kritzinger and Wiart [31] that a rescaled version of the lattice \(\varLambda _\varphi \) was considered several years ago by Thomas Lachmann (unpublished result) as a candidate for an upper bound on the minimum dispersion A(n) of an n-point set in a unit square. Yet another lattice resembling \(\varLambda _\varphi \) was studied in the same context by Ismăilescu [25].
It is easy to check that the lattice \(\varLambda _\varphi \) yields the upper bound \(\liminf _{n \rightarrow \infty } n A(n) \le \varphi ^4/(\varphi ^2+1)\), i.e., matching exactly the dispersion bound obtained by Kritzinger and Wiart using a suitable modification of the so-called Fibonacci lattice [16]. It is worth noting that: (i) the lattice \(\varLambda _\varphi \) yields the above dispersion result with a cleaner and shorter proof; (ii) the Fibonacci lattice as well as its modification lead to this bound only by a limiting process; and perhaps more importantly, (iii) the upper bound in Lemma 2 on the maximum rectangle area amidst points in this lattice holds universally across the entire plane and not only inside a bounding box with n points (i.e., one does not need to worry about rectangles with a side supported by the bounding box boundary).
4 Conclusion
We list several open questions.
-
1.
(Computational complexity.) Given a family \(\mathcal F\) of n axis-parallel rectangles, what is the computational complexity of determining the optimal density \(\pi _T(\mathcal F)\) of a piercing set for all translates of all members in \(\mathcal F\)? (For the decision problem: given a threshold \(\tau \), is there a piercing set whose density is at most \(\tau \)?) Is the problem algorithmically solvable? Is there a polynomial-time algorithm? And how about the complexity of determining the optimal density \(\pi _L(\mathcal F)\) of a piercing lattice for \(\mathcal F\)?
-
2.
(Exact answer for two rectangles.) For two rectangles, what is the actual value of \(\pi _T(w,h)\) (or its reciprocal \(A_T(w,h)\)) when \(\lfloor w\rfloor =\lfloor h\rfloor \ge 2\)? Is it the same as \(\pi _L(w,h)\)?
-
3.
(Other shapes.) How about pairs of different shapes such as triangles?
-
4.
(Congruent copies.) How about requiring that the point set pierces all congruent copies of a set of shapes, not only translates? See for instance [4] where it is shown that when \(\mathcal F\) consists of a single square (or rectangle), a suitable triangular grid gives an upper bound on the density.
-
5.
(Discrete version.) Consider a discrete version where: (i) each shape in the family \(\mathcal F\) consists of cells of an infinite square grid; (ii) we consider translates by integer vectors only; and (iii) instead of piercing with a point set we pierce with a set of grid cells. What can be said about this (lowest possible) discrete hitting density \(\pi _T^{{\text {disc}}}(\mathcal F)\) or its reciprocal \(A_T^{{\text {disc}}}(\mathcal F)\)? As one example, we note that Theorems 1 and 2 can be adapted to the discrete setting in a straightforward way: When \(\mathcal F\) consists of two rectangles \(R_{a\times b}\), \(R_{b\times a}\), where \(b=k\cdot a+r\) (with \(k\ge 1\) and \(r<a\)), the adapted Theorem 1 yields an upper bound \(A_T^{{\text {disc}}}(\{R_{a\times b},R_{b\times a}\})\le k\cdot a^2+r^2\) that solves the puzzle we mentioned in the introduction. Furthermore, when \(\mathcal F\) consists of all rectangles that have area at least K, then the adapted Theorem 2 gives an \(\mathcal F\)-piercing set of cells with density \((1+\frac{2}{5}\sqrt{5})/K\). In the language of Fiat and Shamir [16], there is a probing strategy that locates a battleship of K squares in a rectangular sea of M squares (where \(M \rightarrow \infty \)) in at most \(1.895 \, M/K\) probes. This is a substantial improvement over the \(3.065 \, M/K\) bound from [16]. As another example, when \(\mathcal F\) consists of two L-triominoes that are centrally symmetric to each other, one can show that \(A_T^{{\text {disc}}}(\mathcal F)=3\). In contrast, when \(\mathcal F\) consists of two (or more) L-triominoes, one of which is obtained from another one by rotation by \(90^\circ \), one can show that \(A_T^{{\text {disc}}}(\mathcal F)=2\).
-
6.
(Higher dimensions.) Consider the problem in higher dimensions. When \(d=3\) and \(|\mathcal F|=2\), stretching along the coordinate axis yields a non-trivial case \(\{(a,b,1),(1,1,c)\}\) where \(a,b,c \ge 1\). The trivial upper bound \(A_T(a,b,c)\le \min \{ab,c\}\) can be matched in two “easy” cases: (i) When \(c\ge \left\lceil a \right\rceil \cdot \left\lceil b \right\rceil \) then “piercing \(1\times 1\times c\) is free”: Briefly, in the plane \(z=0\) we use a lattice with basis [a, 0], [0, b] and in the planes \(z\in \mathbb {Z}\) we consider \(\left\lceil a \right\rceil \cdot \left\lceil b \right\rceil \) “integer horizontal offsets” [u, v], \(u=0,\dots ,\left\lceil a \right\rceil -1\), \(v=0,\dots ,\left\lceil b \right\rceil -1\) and use them periodically (in any order). (ii) When \(c\le \left\lfloor a \right\rfloor \cdot \left\lfloor b \right\rfloor \) then “piercing \(a\times b\times 1\) is free”: Briefly, along the line \(x=y=0\) we put points at \(k\cdot \left\lfloor a \right\rfloor \cdot \left\lfloor b \right\rfloor \) for \(k\in \mathbb {Z}\). For other vertical lines through integer points we use \( \left\lfloor a \right\rfloor \cdot \left\lfloor b \right\rfloor \) “integer vertical offsets” such that every \( \left\lfloor a \right\rfloor \cdot \left\lfloor b \right\rfloor \) horizontal grid-rectangle contains all offsets. Together, the easy cases (i) and (ii) cover the case when \(a\in \mathbb {Z}\), \(b\in \mathbb {Z}\), \(c\in \mathbb {R}\) and the case when ab and c “differ by a lot”. Another easy case is \(a=1\), when the planar bounds apply (for two rectangles with sizes \(1\times b\) and \(c\times 1\)). Finally, from the algorithmic standpoint, given a finite collection of axis-parallel boxes in \(\mathbb {R}^d\), what approximations for the piercing density can be obtained?
-
7.
(Disconnected shapes.) What can be said about disconnected shapes? The easiest variant seems to be when each shape is a set of integer points on the line (or in \(\mathbb {Z}^d\)) and we consider translates by integer vectors only. Note that the piercing density and the lattice piercing densities may differ in this case; for instance, when \(S=\{0,2\} \subset \mathbb {Z}\), these densities are 1/2 and 1, respectively. In view of the connection to covering mentioned in Sect. 1, it is worth mentioning that the problem of tiling the infinite integer grid with finite clusters is only partially solved [35]; however, covering is generally easier than tiling.
References
Aistleitner, C., Hinrichs, A., Rudolf, D.: On the size of the largest empty box amidst a point set. Discret. Appl. Math. 230, 146–150 (2017)
Alon, N., Kleitman, D.J.: Piercing convex sets and the Hadwiger-Debrunner \((p, q)\)-problem. Adv. Math. 96(1), 103–112 (1992)
Aronov, B., Ezra, E., Sharir, M.: Small-Size \(\varepsilon \)-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248–3282 (2010)
Basic, B., Slivková, A.: On optimal piercing of a square. Discret. Appl. Math. 247, 242–251 (2018)
Braß, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005). https://doi.org/10.1007/0-387-29929-7
Bukh, B., Chao, T.-W.: Empty axis-parallel boxes, manuscript (2021). arXiv:2009.05820
Carmi, P., Katz, M.J., Lev-Tov, N.: Polynomial-time approximation schemes for piercing and covering with applications in wireless networks. Comput. Geom. Theory Appl. 39, 209–218 (2008)
Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46(2), 178–189 (2003)
Chan, T.M., Mahmood, A.-A.: Approximating the piercing number for unit-height rectangles. In: Proceedings of 17th Canadian Conference on Computational Geometry (CCCG 2005), University of Windsor, Ontario, Canada, pp. 15–18 (2005)
Chudnovsky, M., Spirkl, S., Zerbib, S.: Piercing axis-parallel boxes. Electron. J. Comb. 25(1), #P1.70 (2018)
Correa, J.R., Feuilloley, L., Pérez-Lantero, P., Soto, J.A.: Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity. Discrete Comput. Geom. 53(2), 344–365 (2015)
Danzer, L., Grünbaum, B., Klee, V.: Helly’s theorem and its relatives. In: Proceedings of Symposia in Pure Mathematics, vol. 7, pp. 101–181. American Mathematical Society (1963)
Dumitrescu, A., Jiang, M.: Piercing translates and homothets of a convex body. Algorithmica 61(1), 94–115 (2011)
Eckhoff, J.: A survey of the Hadwiger-Debrunner \((p, q)\)-problem. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete & Computational Geometry. Algorithms and Combinatorics, vol. 25, pp. 347–377. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-642-55566-4_16
Fejes Tóth, G.: Packing and covering. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.) Handbook of Discrete and Computational Geometry (Chapter 2), 3rd edn, pp. 27–66. CRC Press, Boca Raton (2017)
Fiat, A., Shamir, A.: How to find a battleship. Networks 19, 361–371 (1989)
Fon-Der-Flaass, D., Kostochka, A.V.: Covering boxes by points. Discret. Math. 120(1–3), 269–275 (1993)
Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12, 133–137 (1981)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
Govindarajan, S., Nivasch, G.: A variant of the Hadwiger-Debrunner \((p, q)\)-problem in the plane. Discrete Comput. Geom. 54(3), 637–646 (2015)
Hadwiger, H., Debrunner, H.: Combinatorial Geometry in the Plane (English translation by Victor Klee). Holt, Rinehart and Winston, New York (1964)
Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford University Press, Oxford (1979)
Helly, E.: Über Mengen konvexer Körper mit gemeinschaftlichen Punkten. Jahresber. Deutsch. Math.-Verein. 32, 175–176 (1923)
Holmsen, A., Wenger, R.: Helly-type theorems and geometric transversals. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.) Handbook of Discrete and Computational Geometry (Chapter 4), 3rd edn, pp. 91–123. CRC Press, Boca Raton (2017)
Ismăilescu, D.: Personal communication (2019)
Karasev, R.N.: Transversals for families of translates of a two-dimensional convex compact set. Discret. Comput. Geom. 24, 345–353 (2000)
Károlyi, G.: On point covers of parallel rectangles. Period. Math. Hung. 23(2), 105–107 (1991)
Károlyi, G., Tardos, G.: On point covers of multiple intervals and axis-parallel rectangles. Combinatorica 16(2), 213–222 (1996)
Kim, S.-J., Nakprasit, K., Pelsmajer, M.J., Skokan, J.: Transversal numbers of translates of a convex body. Discret. Math. 306, 2166–2173 (2006)
Krieg, D.: On the dispersion of sparse grids. J. Complex. 45, 115–119 (2018)
Kritzinger, R., Wiart, J.: Improved dispersion bounds for modified Fibonacci lattices. J. Complex. 63, 101522 (2021). https://doi.org/10.1016/j.jco.2020.101522
Mustafa, N., Varadarajan, K.: Epsilon-nets and epsilon-approximations. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.) Handbook of Discrete and Computational Geometry (Chapter 47), 3rd edin. CRC Press, Boca Raton (2017)
Olds, C.D.: Continued Fractions. Random House, New York (1963)
Sosnovec, J.: A note on minimal dispersion of point sets in the unit cube. Eur. J. Comb. 69, 255–259 (2018)
Szegedy, M.: Algorithms to tile the infinite grid with finite clusters. In: Proceedings of 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), Palo Alto, California, USA, pp. 137–147. IEEE Computer Society (1998)
Ullrich, M., Vybíral, J.: An upper bound on the minimal dispersion. J. Complex. 45, 120–126 (2018)
Acknowledgments
We would like to thank Wolfgang Mulzer and Jakub Svoboda for helpful comments on an earlier version of this work.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Dumitrescu, A., Tkadlec, J. (2021). Piercing All Translates of a Set of Axis-Parallel Rectangles. In: Flocchini, P., Moura, L. (eds) Combinatorial Algorithms. IWOCA 2021. Lecture Notes in Computer Science(), vol 12757. Springer, Cham. https://doi.org/10.1007/978-3-030-79987-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-79987-8_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-79986-1
Online ISBN: 978-3-030-79987-8
eBook Packages: Computer ScienceComputer Science (R0)