Piercing Pairwise Intersecting Convex Shapes in the Plane

Abstract

Let C be any family of pairwise intersecting convex shapes in a two dimensional Euclidean space. Let $\tau (C)$ denote the piercing number of C, that is, the minimum number of points required such that every shape in C contains at least one of these points. Define a shape to be $\alpha$-fat when the ratio of the radius of the smallest disk that encloses the shape over the radius of the largest disk that is enclosed in the shape is at most $\alpha$. Define $\alpha (C)$ to be the minimum value where each shape in C is $\alpha (C)$-fat. We prove that $\tau (C) \le 43.789\alpha (C) + 4 = O(\alpha (C))$ for any set C consisting of pairwise intersecting convex $\alpha$-fat shapes. This improves the previous best known upper-bound of $O(\alpha (C)^2)$. This result has a number of implications on other results concerning fat shapes, such as designing data structures with less complexity for 3-D vertical ray shooting and computing depth orders. Additionally, our results reduce the time complexity of the query time of these data structures. We also get better bounds for some restricted families of shapes. We show that $(5\sqrt{2}+2)\alpha (C)+ 25 + 5\sqrt{2} \le 9.072\alpha (C) + 32.072 = O(\alpha (C))$ piercing points are sufficient to pierce a set of arbitrarily oriented $\alpha$-fat rectangles. We also prove that $\tau (C) = 2$ when C is a set of pairwise intersecting homothets of regular hexagons. We show that the piercing number of a set of pairwise intersecting homothets of an arbitrary convex shape is at most 15. This improves the previous best upper-bound of 16. We also give an algorithm to calculate the exact location of the piercing points.

Research supported in part by NSERC.

1 Introduction

Let H be a set of convex shapes in $d-$dimensions such that every subset of $d+1$ shapes in H has a non-empty intersection. In 1923, Helly [11] proved that the intersection of all shapes in H is non-empty. This result is known as the Helly’s theorem. For example, if H is a set of convex shapes in $\mathbb {R}^2$ such that every three of them have a common intersection, then by Helly’s theorem all shapes in H have a common intersection. In the other words, all shapes in H can be pierced with one point.

Consider the following fundamental geometric problem: What is the minimum number of points that is sufficient to pierce a given set of pairwise intersecting shapes in the plane? In the case of homothetic triangles, three points are sufficient, as was shown by Chakerian et al. (1967) [5]. In the case of disks, four points are sufficient. The proof of the existence of four piercing points was independently shown by Danzer (1956, 1986) [6] and Stacho (1981) [23, 24]. To pierce a set of n pairwise intersecting line segments, $\varOmega (n)$ points are sometimes required. This huge gap between the number of points required, from a constant to linear, to pierce different sets of pairwise intersecting shapes gives rise to many interesting problems. Notice that the linear lower-bound to pierce a set of pairwise intersecting line segments comes from the fact that line segments are essentially “thin”. How round or fat an object is plays a vital role in the number of points needed to pierce the set. The main problem that we study in this paper is the following: How many points are sufficient to pierce a set of pairwise intersecting shapes in terms of their fatness parameter?

In the literature, the main approach used by researchers to pierce a set C of pairwise intersecting $\alpha$-fat shapes is by constructing a grid whose resolution is quadratic in the fatness parameter [2, 14, 18, 19]. In this article, we are able to reduce the number of points to linear with respect to the fatness parameter by placing points near the perimeter of a shape that has a non-empty intersection with every other shape in the set. In essence, we show that it is possible to pierce the set by focusing on the perimeter of an object as opposed to filling an area with points. The details of our approach are given in Sect. 2.

1.1 Preliminaries

Informally the fatness of a shape is a parameter that tries to capture how close a shape is to a disk. There are many different definitions and variations of the fatness of a shape [1, 7, 15, 17, 19, 20, 25]. Most of them share some similarities. In this paper we use the following measure of fatness. The fatness of a shape c is the ratio of the radius of the smallest disk that encloses c over the radius of the largest disk that is enclosed in c. This measure of fatness will be denoted by $\alpha$. We say that a shape c is $\alpha$-fat if its fatness is at most $\alpha$. A set C of shapes is referred to as $\alpha (C)$-fat if $\alpha (C)$ is the smallest value such that $\forall c_i$ $\in C$, the fatness of $c_i$ is lesser than or equal to $\alpha (C)$. We note that a set of disks is 1-fat, since a disk is perfectly fat according to our fatness definition.

The piercing number of a family of sets $\mathcal {F}$ is the smallest integer k for which it is possible to partition $\mathcal {F}$ into subfamilies $\mathcal {F}_1,\dots ,\mathcal {F}_k$ such that the sets in each $\mathcal {F}_i$ have a non-empty intersection for every i such that $1 \le i \le k$ [8]. We say that a set of points P pierces a set of shapes C if every shape in C contains at least one point of P.

A shape B is a homothet of a shape A if B can be obtained by scaling and translating the shape A. Two geometric figures are homothetic if one is a homothet of the other. If every pair of shapes in a set C is homothetic we call the set C homothets. In this paper we only consider positive homotheties. A set of shapes C is unit if all the shapes in C have the same area.

1.2 Our Contributions

In this paper we prove the following results in 2-dimensions:

• Any set C of pairwise intersecting arbitrary convex shapes with fatness $\alpha (C)$ can be pierced with less than or equal to $43.789\alpha (C) + 4 \in O(\alpha (C))$ points.

• Any set C of pairwise intersecting rectangles of arbitrary orientation with fatness $\alpha (C)$, can be pierced by $(5\sqrt{2}+2)\alpha (C)+ 25 + 5\sqrt{2} \in O(\alpha (C))$ points.

• Any set of pairwise intersecting convex homothets can be pierced by 15 points.

• A set of pairwise intersecting homothets of regular hexagons can be pierced by 2 points.

Known results for piercing sets of pairwise intersecting convex sets.
Family of convex shapes	Known results	Our results
Homothetic Triangles	3 Points [5]	_
Homothetic Rectangles	1 Point [folklore]	_
Homothetic regular Hexagons	Not known	2 Points, Theorem 4
Disks	4 Points [6, 21, 23, 24]	_
Centrally symmetric	7 Points [9]	_
Unit Shapes	3 Points [12]	_
Convex Homothets	16 [16]	15 Points, Theorem 3
$\alpha$-fat Rectangles	$O(\alpha ^2)$ [2, 14, 18, 19]	$\le 9.072$ $\alpha +32.072$, Theorem 2
$\alpha$-fat Convex shapes	$O(\alpha ^2)$ [2, 14, 18, 19]	$\le 43.789$ $\alpha$ + 4, Theorem 1

1.3 Previous Results

Overmars et al. (1994) [19] proved that for a set of disjoint convex $\alpha$-fat objects and a restricted range query (with diameter $h\times p$ where h is a constant and p is the radius of the minimal enclosing hyper-sphere among the objects in the set) in d-dimensions, $O((\alpha d^dh)^d)$ points are enough to pierce all the shapes. They use a grid of points inside and around the range query to pierce such a set. Agarwal et al. (1995) [2], Katz (1996) [14] and Nielsen (2000) [18] among other results proved that $O(\alpha ^2)$ points can pierce a set of pairwise intersecting $\alpha$-fat shapes in 2-dimension. The definitions of fatness that they use are similar. The unifying theme among these proofs is to cover the area around and inside the smallest shape with a grid of $\varTheta (\alpha ^2)$ piercing points. To find the piercing points Nielsen (2000) [18] uses Fredman’s sampling technique [14]. Agarwal et al. (1995) [2], Katz (1996) [14] use a similar gridding technique.

Let F be a family of pairwise intersecting and centrally symmetric convex homothets. Grünbaum (1959) [9] showed that $\tau (F)$¹ $\le 7$. He transforms all the shapes from Euclidean space into Minkowski space. The reason behind this transformation is that any centrally symmetric shape in Euclidean space can be treated as a disk in Minkowski space. This transformation maintains the pairwise intersecting property of the set. The fact that 4 points pierces a set of pairwise intersecting disks applies [6, 21, 23, 24]. Grünbaum (1959) [9] also showed that $\tau (F) = 3$ when F is a family of pairwise intersecting and centrally symmetric convex unit-shapes. He conjectured that $\tau (F) = 3$ for any family of pairwise intersecting convex unit-shapes. This conjecture was proved by Karasev (2000) [12]. Karasev (2001) [13] subsequently showed an upper-bound of $d+1$ on the number of points sufficient to pierce a family of d-wise intersecting homothets of a simplex in $\mathbb {R}^d$. He also gave an upper-bound for a family F of d-wise intersecting spheres which is the following: $\tau (F) \le 3(d+1)$ when $d\ge 5$ and $\tau (F) \le 4(d+1)$ when $d\le 4$.

In case of pairwise intersecting disks, Danzer (1956, 1986) [6] and Stacho (1981) [23, 24] were the first to give a proof of the existence of 4 piercing points. However, both of their proofs are essentially non-constructive. Har-Peled et al. [10] were the first to present a deterministic and constructive algorithm. They find 5 piercing points, in O(n) expected time, that pierces a set of n pairwise intersecting disks. Biniaz, Bose and Wang [3] gave a linear algorithm that finds 5 piercing points given a set of pairwise intersecting disks that does not use an LP-type framework unlike Har-Peled’s algorithm. Carmi, Katz and Morin [21] gave a linear time algorithm to compute 4 piercing points which also uses LP-type machinery.

2 General Convex Shapes

2.1 Piercing a Set of Fat Shapes

In this section we prove the following theorem which is our main result.

Theorem 1

Any set C of pairwise intersecting arbitrary convex shapes on a plane with fatness $\alpha (C)$ can be pierced with $(12+6\sqrt{2}+2^{\frac{15}{4}}\sqrt{3})\alpha (C) + 4 \le 43.789\alpha (C) \in O(\alpha (C))$ points.

Fig. 1.

outer case

Fig. 2.

Initial setup and information required for the proof

Proof

(Proof of Theorem 1 ).

Let $S = \{S_0, S_1, \dots , S_{n-1}\}$ be a set of pairwise intersecting convex shapes with fatness at most $\alpha$. For all i, let $\alpha _{i}$ be the fatness of $S_i$. Let o be the smallest disk that has a non empty intersection with every shape in the set S. Let $\delta$ be the radius of o. Define $sq_{1}$ to be an axis-parallel square that is concentric with o. Let the side length of $sq_{1}$ be $2c\delta$ for a constant c. And let $sq_2$ be an axis-parallel square concentric with o with side length $2c_1\delta$ for a constant $c_1$ ($c_1 > c$). We specify the exact values of c and $c_1$ at the end of the proof (Fig. 2).

If all the shapes in S have a common intersection we can pierce the whole set with one point and as a result o will have radius zero. Otherwise, o is tangent to at least three shapes, say $S_1$, $S_2$, $S_3$. Let $L_1, L_2, L_3$ be the three tangent lines to o where $S_1$, $S_2$, $S_3$ intersect o. Notice that no two tangent line can be parallel, otherwise, either the intersection of every shape in S is non-empty or it contradicts the fact that two corresponding shapes intersect. Moreover, $L_1, L_2, L_3$ form a triangle, otherwise it contradicts with the minimality of o (See Fig. 2).

We partition the set S into two groups, $S^{gp1}$ and $S^{gp2}$. A shape $S_i \in S$ will be in $S^{gp1}$ if the center of the largest enclosed disk in $S_i$ or at least one of the largest enclosed disks in $S_i$ (in case $S_i$ has multiple largest enclosed disks) is located completely outside of $sq_1$. Otherwise, $S_i$ will be in $S^{gp2}$.

Piercing $S^{gp1}$: By the definition of o, every shape in $S^{gp1}$ intersects o. Every shape $S_i$ in $S^{gp1}$ is convex, intersects o and has at least one of the largest disk(s) enclosed in $S_i$ centered outside of $sq_1$. These three facts plus the fact that $sq_1$ encloses o implies that $S_i$ intersects a continuous portion of the boundary of $sq_1$. We now show how to place a set of points on the boundary of $sq_1$ to pierce all the shapes in $S^{gp1}$. Let $S_i$ be an arbitrary shape in $S^{gp1}$. Let $p^{*}$ be an arbitrary point in the intersection of $S_i$ and the boundary of o. Let $o'$ be the largest disk enclosed in $S_i$ and centered outside of $sq_{1}$(in the case of multiple disks satisfying these conditions, pick an arbitrary one). Without loss of generality, assume that $S_i$ intersects the right vertical side of $sq_1$. Let ab be the diameter of $o'$ parallel to the y-axis. Since $S_i$ is convex, there exists a triangle $p^{*}ab$ that is contained in $S_i$. Let the boundary of the triangle $p^{*}ab$ cross the boundary of $sq_1$ at points $a'$ and $b'$. Now the minimum possible length of the segment $a'b'$ gives us the required resolution of points to put on the boundary of $sq_1$ to pierce $S^{gp1}$. Recall that $\alpha _{i}$ is the fatness of $S_i$. The smallest disk that encloses $S_i$ has a radius greater than or equal to $\frac{|p^*b|}{2}$ since the segment $p^*b$ is in $S_i$ and any disk with diameter less than $|p^*b|$ cannot have a segment of length $|p^*b|$ in it. Thus, $\alpha _{i} \ge \frac{\frac{|p^*b|}{2}}{\frac{|ab|}{2}} = \frac{|p^*b|}{|ab|}$. Moreover, since the two triangles $p^*ab$ and $p^*a'b'$ are similar we get following equation: $\frac{|a'b'|}{|p^*b'|} = \frac{|ab|}{|p^*b|} \implies |a'b'| = \frac{|ab| \cdot |p^*b'|}{|p^*b|} \implies |a'b'| \ge \frac{|p^*b'|}{\alpha _{i}}$. Furthermore, note that $(c-1)\delta \le |p^*b'| \le 2\sqrt{2}c\delta$ and $\alpha (S) \ge \alpha _{i}$. (“Therefore, $|a'b'|$ is at least $\frac{(c-1)\delta }{\alpha (S)}$. See Fig. 1”).

Exceptional Case: The only exceptional case in this scenario is when $a'$ is not located on the same side of $sq_1$ as $b'$. Considering the fact that the disk $o'$ is centered outside of $sq_1$, the convexity of $S_i$ implies that $S_i$ contains a corner of $sq_1$. To pierce such shapes we put points on the 4 corners of $sq_1$.

The perimeter of $sq_1$ is $8c \delta$, therefore the number of points placed on the perimeter of $sq_1$ to pierce all the shapes in $S^{gp1}$ is $4 + \frac{8c \delta }{\frac{(c-1)\delta }{\alpha (S)}} = 4 + \frac{8c}{c-1}\alpha (S)$

Piercing $S^{gp2}$: Let $S_i$ be an arbitrary shape in $S^{gp2}$. Let $L_{i}^{'}$ be a line through the center of circle o and parallel to $L_i$ for $i \in \{1, 2, 3\}$. We call a point p proper with respect to $L_i, i\in [1,3]$ if it is located inside $sq_2$, and p is located on the same side of $L_i$ and $L_{i}^{'}$ but p is closer to $L_{i}^{'}$.

Lemma 1

Any point inside $sq_2$ is proper with respect to some $L_i, i\in [1, 3]$.

Proof

Let $H_i, i\in [1,3]$ be the halfspace that is tangent to $L_{i}^{'}$ and does not contain $L_i$. Since $H_1, H_2, H_3$ intersect at a point and the union of the angle that they cover is $2\pi$ (otherwise it contradicts with the fact $L_1, L_2, L_3$ form a triangle). Using the result of Bose et al. [4] we have that the $\cup H_i,$ for $i\in [1,3]$ covers the entire plane. Thus, they cover any point in $sq_1$ as well.    $\square$

The number of points sufficient to pierce the set

Without loss of generality, assume that the center of at least one of the largest disks enclosed in $S_i$ is a proper point with respect to $L_1$. Such a disk exists, since, at least one of the largest disks enclosed in $S_i$ is centered in $sq_1$.

(“We analyze two cases, namely when $S_i \cap L_1 \cap sq_2 \ne \emptyset$ and when $S_i \cap L_1 \cap sq_2 = \emptyset$. See Fig. 3 and 4”)

• Case 1. $S_i$ has an intersection with $L_1$ inside $sq_2$.

  Let $p^*$ be an arbitrary point in the intersection of $L_1$ and $S_i$ interior to $sq_2$. Let $o'$ be a largest disk enclosed in $S_i$ centered inside $sq_1$. Let ab be the diameter of $o'$ parallel to $L_1$. Since the center of $o'$ is proper point with respect to $L_1$, the triangle $p^*ab$ intersects $L_{1}^{'}$ at two points $a'$ and $b'$. Recall that $\alpha _{i}$ is the fatness of $S_i$, the smallest disk that encloses $S_i$ has a radius greater than or equal to $\frac{|p^*b|}{2}$, since the segment $p^*b$ is in $S_i$ and any disk with diameter less than $|p^*b|$ cannot have a chord of length $|p^*b|$. Thus, $\alpha _{i} \ge \frac{\frac{|p^*b|}{2}}{\frac{|ab|}{2}} = \frac{|p^*b|}{|ab|}$. Moreover, since the triangles $p^*ab$ and $p^*a'b'$ are similar we get the following equation: $\frac{|a'b'|}{|p^*b'|} = \frac{|ab|}{|p^*b|} \implies |a'b'| = \frac{|ab|.|p^*b'|}{|p^*b|} \implies |a'b'| \ge \frac{|p^*b'|}{\alpha _{i}}$. By definition and the relation between $L_1$ and $L_{1}^{'}$, $\delta \le |p^*b'| \le 2\sqrt{2}c\delta$ and $\alpha (S) \ge \alpha _{i}$. Therefore, $|a'b'| \ge \frac{\delta }{\alpha (S)}$. The length of $L_{1}^{'}\cap sq_2$ is at most $2\sqrt{2}c_1\delta$, which is the diameter of $sq_2$. Hence, we place $\frac{2\sqrt{2} c_1 \delta }{\frac{\delta }{\alpha (S)}} = 2\sqrt{2} c_1 \alpha (S)$ points on $L_{1}^{'}$. So, in total $6\sqrt{2} c_1 \alpha (S)$ points on $L_{1}^{'}, L_{2}^{'}, L_{3}^{'}$ are sufficient to pierce shapes in this case.

• Case 2. $S_i$ only intersects $L_1$ outside of $sq_2$.

  As a result $S_i$ intersects with the boundary of $sq_2$. Let $p^*$ be a point in the intersection of $S_i$ and the boundary of $sq_2$. Without loss of generality, assume that $p^*$ is located on the right side of $sq_2$. Let $o'$ be a largest disk enclosed in $S_i$ centered inside $sq_1$. Let ab be the diameter of $o'$ parallel to the y-axis. Recall that $\alpha _{i}$ is the fatness of $S_i$. The smallest disk that encloses $S_i$ has a radius greater than or equal to $\frac{|p^*b|}{2}$. By an identical argument as in Case 1, we have $|a'b'| = \frac{|ab|.|p^*b'|}{|p^*b|} \implies |a'b'| \ge \frac{|p^*b'|}{\alpha _{i}}$. By definition of $sq_1, sq_2$ and $P^*a'b'$; $(c_1-c)\delta \le |p^*b'| \le 2\sqrt{2}c_1\delta$ and $\alpha (S) \ge \alpha _{i}$. Therefore, the minimum length of $|a'b'|$ is $\frac{(c_1-c)\delta }{\alpha (S)}$. The perimeter of $sq_1$ is $8c\delta$, therefore the number of points required to put on the perimeter of $sq_1$ is $\frac{8c \delta }{\frac{(c_1-c)\delta }{\alpha (S)}} = \frac{8c}{c_1-c}\alpha (S)$.

Let $m = max(\frac{c}{c_1-c}, \frac{c}{c-1})$. The number of points sufficient to pierce the set S using the placements described above is $4 + (8m + 6\sqrt{2}c_1)\alpha (S)$. The minimum value is roughly 43.789 when we set $c = 1.6866$ and $c_1 = 2.3732$.    $\square$

Fig. 3.

A convex shape with the largest enclosed disk centered in $sq_1$ and intersecting $L_1$ inside $sq_2$

Fig. 4.

A convex shape with the largest enclosed disk centered in $sq_1$ and intersecting $L_1$ only outside of $sq_2$

2.2 Implications

Our result has a number of implications on other research problems concerning sets of fat objects, such as computing depth orders, 3-D vertical ray shooting, 2-D point enclosure, range searching, and arc shooting for convex fat objects. The following are some Corollaries where the asymptotic complexity is improved from $O(\alpha ^2)$ to $O(\alpha )$ using our results:

• 1. Piercing a set of pairwise intersecting c-oriented convex polygons [18]

Corollary 1

The piercing number $\tau (\beta )$ when $\beta$ is a set of pairwise intersecting c-oriented $\alpha$-fat polygons is $O(\alpha )$.

• 2. Computing depth order for fat objects [2]

Corollary 2

The time complexity of 2-dimensional linear-extension problem is of $O(\alpha n\lambda ^{1/2}_s (n) \log ^4 n)$.

• 3. 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects [14]

Corollary 3

For a given query point p, the object of C lying immediately below p (if such an object exists) can be found in $O(\alpha \log ^4 n)$ time.

Corollary 4

For a given query point p, the k objects of C containing p can be reported in $O(\alpha \log ^3 n + k \log ^2 n)$ time.

2.3 Piercing Fat Rectangles

In this section we demonstrate how to pierce a set C of pairwise intersecting rectangles of arbitrary orientation with fatness $\alpha (C)$. This theorem is a generalization of pairwise intersecting line segments in terms of fatness.

Theorem 2

Any set C of pairwise intersecting rectangles of arbitrary orientation of fatness $\alpha (C)$ can be pierced with $(5\sqrt{2}+2)\alpha (C)+ 25 + 5\sqrt{2} \le 9.072\alpha (C) + 32.072 = O(\alpha (C))$ points.

Lemma 2

The maximum area of a square that does not have any lattice point in it is less than 2. A lattice point is a point with integer coordinates.

Proof

(Proof of Theorem 2). Let $R = \{r_0, r_1, ..., r_{n-1}\}$ be a set of pairwise intersecting rectangles. Denote a rectangle r of width w and height h as (w, h). We assume that the longer side of an arbitrary oriented rectangle is the height of the rectangle ($h \ge w$). Without loss of generality, Let $r_1 = (w_1, h_1)$ be the rectangle with the minimum width among all rectangles in the set R. Without loss of generality, assume that $r_1$ is axis parallel.

Structure of the grid points: Let $r_i =$ $(w_i, h_i)$ be an arbitrary rectangle in R, let $p^*$ be one of the intersection points of the boundary of $r_1$ with $r_i$. By definition of $r_1$ we have the following two inequalities: $w_i \ge w_1$ and $h_i \ge w_1$. For every $r_i \in R$ there exists a square $s_i$ located inside $r_i$ of side length $w_1$ such that, $s_i$ contains the point $p^*$. Suppose that such a square does not exist. It implies that any square of side length $w_1$ that contains $p^*$ intersects with the boundary of $r_i$. Thus, either $w_i < w_1$ or $h_i < w_1$, both of which contradicts with the minimality of $w_1$.

Let G be a grid of points whose resolution is 1. Let $G'$ be a grid of points whose resolution is $\frac{w_1}{\sqrt{2}}$. By Lemma 2 we see that any square of side length at least $w_1$ must contain at least one point of $G'$ (To see the argument simply scale down the squares and $G'$ by factor of $\frac{w_1}{\sqrt{2}}$). By definition, every $s_i$ intersects $r_1$, and, the distance from any point in any $s_i, i\in [0,n-1]$ to the boundary of $r_1$ is at most $\sqrt{2}w_1$(in the worst case the point can be on the opposite side of the diameter of a square). Therefore, we cover an axis-parallel rectangle centered with $r_1$, whose distance to $r_1$ is at most $\sqrt{2}w_1$, with a grid of points. See Fig. 5 for illustration. That rectangle has width $w_1 + 2\sqrt{2}w_1$ and height $h_1 + 2\sqrt{2}w_1$. Therefore, The number of the grid points $(\frac{w_1 + 2\sqrt{2}w_1}{\frac{w_1}{\sqrt{2}}} + 1) \times (\frac{h_1 + 2\sqrt{2}w_1}{\frac{w_1}{\sqrt{2}}}+1) = (\sqrt{2} + 5) \times (\sqrt{2}\frac{h_1}{w_1} + 5) \le (5\sqrt{2}+2)\alpha (C)+ 25 + 5\sqrt{2}$. Therefore, the sufficient number of points on the grid to pierce the set C is $(5\sqrt{2}+2)\alpha (C)+ 25 + 5\sqrt{2}$ that is less than or equal to $9.072\alpha (C) + 32.072$.    $\square$

Fig. 5.

How an arbitrary rectangle in R gets pierced by a point on the grid.

3 Refined Results for Specific Shapes

In this section we study the number of points sufficient to pierce more specific sets of shapes. First we study sets of pairwise intersecting homothets and design an algorithm that computes the exact location of the points that pierce the set. Next, we show that 2 points are sometimes necessary and always sufficient to pierce a set of pairwise intersecting homothets of a regular hexagon.

3.1 Homothets of a Convex Shape

In this subsection, we show how one can pierce any set of pairwise intersecting homothetic shapes with a constant number of points. More precisely, we give an upper-bound of 15 piercing points. Kim et al. [16] proved that 16 points are sufficient to pierce any set of pairwise intersecting homothetic convex shapes. Kim’s proof [16][Lemmas 4,13] requires the existence of two homothetic parallelotopes $p_A$ and $P_A$ such that $p_A \subseteq A \subseteq P_A$ where A is a convex shape. In this paper, our parallelotopes of choice are the pair of rectangles provided by Schwarzkopf et al.’s [22] Algorithm. This pair of rectangles satisfies the required conditions for Kim’s [16] proof. Let S be a set of pairwise intersecting homothetic shapes. We prove that 15 points are enough by eliminating one of the 16 points. Finally, given a set S of n k-gons, we give an algorithm of complexity $O(n + \log ^2k)$ to find the exact location of 16 piercing points and $O(n\log k + \log ^2k)$ to find 15 piercing points.

Let $S = \{S_0, S_1,\dots ,S_{n-1}\}$ be a set of pairwise intersecting homothetic convex shapes in the plane. We transform every shape $S_i \in S$ into a pair of homothetic orthogonal rectangles ($r_i, R_i$), with each pair satisfying the following three conditions: First, $r_i$ is enclosed in $S_i$, and, $R_i$ encloses $S_i$. Second, the side length of $r_i$ is at least half of the side length of $R_i$. Third, the vertices of $r_i$ are located on the boundary of $S_i$.

For a shape $S_i$, define $C_i$ to be a cross-shaped polygon with edges parallel to the edges of $r_i$, with $r_i \subseteq S_i \subseteq C_i \subseteq R_i$. Let $V_i$ be the vertices of $C_i$ which include the vertices of $r_i$ (Fig. 6).

Fig. 6.

$r_i$ and $C_i$ are enclosed in $S_i$ and $R_i$

The existence of such a pair of enclosed and enclosing rectangles for any convex shape was shown by Schwarzkopf et al. [22]. They designed an algorithm to compute such a pair for a convex polygon in time $O(\log ^2 k)$ when the k vertices of the polygon are given in an array and sorted in a lexicographic order.

Let $S^*$ be the smallest shape homothetic to the shapes in S that intersects every shape in S. Assume that $\cap _{i=0}^{n-1} S_i = \emptyset$. Minimality of $S^*$ implies that there exist at least 3 shapes in S, say $S_1, S_2, S_3$, that are tangent to $S^*$ at points $x_1, x_2, x_3$. Let $L_1, L_2, L_3$ be the tangent lines to $S^*$ at $x_1, x_2, x_3$. These three lines form a triangle. For simplicity we assume that $S^*$ is an element of S.

Theorem 3

Any set of pairwise intersecting convex homothets can be pierced by 15 points.

Before proving this theorem, we prove a few helper lemmas. According to Kim et al. [16] the 16 piercing points form a grid (see Fig. 7). We label the points from 1 to 16 starting at the top left point. We show that a corner point can be removed from this set of piercing points. Let $(r^*, R^*)$ be the corresponding rectangles to $S^*$. According to Kim et al. [16] points $\{6, 7, 10, 11\}$ are vertices of $r^*$.

Fig. 7.

Dividing the space into different regions and the area that the intersection of $S_4$ and $S_6$ cannot be.

Every shape in S contains at least one of these 16 piercing points. If there is no shape in the set S that contains only one corner piercing point (points 1, 4, 13, 16) we can simply remove one of the corner points and reduce the piercing number to 15. Otherwise, without loss of generality, let $S_4($resp. $S_5, S_6, S_7)\in S$ be a shape that only contains the point 13 (resp. 1, 4, 16).

Let $H_{i,j}^{k, +}$(resp. $H_{i,j}^{k, -}$) be a halfspace defined by the line that goes through the piercing points i, j and, contains the piercing point k (resp. does not contain the point k).

Let $Region_1$ (resp. $Region_2$, $Region_3$, $Region_4$) be the area defined as $H_{5, 7}^{4, +} \cup H_{7, 15}^{4, +}$ (resp. $H_{7, 15}^{4, +} \cup H_{10, 12}^{13, +}$, $H_{2, 10}^{13, +} \cup H_{10, 12}^{13, +}$, $H_{5, 7}^{4, +} \cup H_{2, 10}^{13, +}$). Let $Region_1^{1}$ be $H_{1, 5}^{4, -} \cap H_{1, 2}^{13, -}$. Let $Region_1^{2}$ be $H_{15, 16}^{4, -} \cap H_{12, 16}^{13, -}$. Let $Region_1^{3}$ be $Region_1 \cap (H_{1, 5}^{4, +} \cap H_{15, 16}^{4, +})$ and $Region_2^{3}$ be $Region_2 \cap (H_{1, 2}^{13, +} \cap H_{12, 16}^{13, +})$.

Lemma 3

$S_4\cap S_6 \not \subseteq Region_1^{1} \cup Region_1^{2}$.

Proof

Let $p \in S_4 \cap S_6$. Suppose, for the sake of a contradiction, $p\in Region_1^{2}$.

Let $p' \in S_4 \cap S^*$ and let $p'' \in S_6 \cap S^*$.

• Suppose that p is not located in $Region_1^{2}\cap H_{3, 8}^{4, +}$.

  In this case the triangle formed by 4, $p''$ and p will contain point 8, which is a contradiction to the definition of $S_6$.

• Suppose that p is not located in $Region_1^{2}\cap H_{9, 14}^{13, +}$.

  Similarly, in this case the triangle formed by 13, $p'$ and p will contain point 14, which is a contradiction to the definition of $S_4$.

Since $H_{3,8}^{4, +}$ and $H_{9, 14}^{13, +}$ have an empty intersection, it implies that the point p cannot be in $Region_1^{2}$. The same argument holds for $Region_1^{1}$. Thus, $S_4$ and $S_6$ cannot intersect in $Region_1^{1}$ either.

   $\square$

Lemma 4

$S_4 \cap Region_1^{3}=\emptyset$.

Proof

Let p be a point on the boundary of $Region_1^{3} \cap S_4$. Let $S_4^{'}$ be a shape homothetic to $S_4$ with the following conditions:

• 1. $S_4^{'}$ has the same size as $S^*$.

• 2. $S_4^{'}$ has p on its boundary.

• 3. $S_4^{'}$ is contained in $S_4$.

Let $C_4^{'}$ be the cross shaped polygon corresponding to $S_4^{'}$. Let ($r_4^{'}$, $R_4^{'}$) be the pair of enclosed and enclosing rectangle corresponding to $S_4^{'}$. Let v be the top right vertex of $r_4^{'}$. By the definition of $S_4^{'}$, v cannot be inside of the rectangle defined by piercing points 9, 10, 13, 14. Otherwise, it contradicts $C_4^{'}$ having an intersection with the boundary of $Region_1^{3}$.

• (“If v is below point 13 then the triangle defined by point 13, p and v contains the piercing point 14. See Fig. 8”).

• If v is to the left of point 13 then the triangle defined by point 13, p and v contains the piercing point 9.

• If v is to the right and above the piercing point 13, then since the resolution of the piercing points and resolution of the vertices that define $r_4^{'}$ (size of $r_4^{'}$) are equal it implies that $r_4^{'}$ as well as $S_4$ contains another piercing point beside point 13. See Fig. 8.

   $\square$

Fig. 8.

$S_4$ does not have an intersection with $Region_1^{3}$

A similar argument holds for $S_6 \cap Region_2^{3}$. Lemmas 3 and 4 imply that $S_4 \cap S_6$ is located in the rectangle formed by piercing points 6, 7, 10, 11.

Lemma 5

$S_4 \cap Region_1$ has an empty intersection.

Proof

Let p be a point from the intersection of the boundary of $Region_1$ and $S_4$. Notice that $Region_1 = Region_1^{3} \cup (H_{11, 15}^{4, +} \cap H_{15, 16}^{4, -}) \cup (H_{1, 5}^{4, -} \cap H_{5, 6}^{4, +})$. Suppose that $S_4$ intersects $Region_1$. We analyze the following three cases:

• 1. $p \in Region_1^{3}$: According to Lemma 3, p cannot be in $Region_1^{3}$

• 2. $p \in H_{11, 15}^{4, +} \cap H_{15, 16}^{4, -}$: Let $p'$ be a point from the intersection of $S_4$ and $S_6$. $S_4 \cap S_6$ is located in the rectangle formed by vertices 6, 7, 10, 11. This means that $p'$ is to the right of point 14. And it implies that the triangle formed by points 13, p and $p'$ contains point 14 which is a contradiction to the definition of $S_4$.

• 3. $p \in H_{1, 5}^{4, -} \cap H_{5, 6}^{4, +}$: Let $p'$ be a point from the intersection of $S_4$ and $S_6$. $S_4 \cap S_6$ is located in the rectangle formed by vertices 6, 7, 10, 11. This means that $p'$ is above point 9. And it implies that the triangle formed by points 13, p and $p'$ contains point 9 which is a contradiction to the definition of $S_4$.

Thus, $S_4$ has an empty intersection with $Region_1$.    $\square$

For a region Reg, let $\overline{Reg}$ be the complement of the region Reg. More precisely, $\overline{Reg} = \{x | x \notin Reg, \forall x\in \mathbb {R}^2\}$.

Notice that $S_1, S_2, S_3$ are tangent to $S^*$. Also, $S_4$ intersects with $S_1, S_2, S_3$ and $S^*$. These two facts imply that $S_4$ intersects with $L_1, L_2$ and $L_3$. Moreover, Lemma 5 implies that the intersection of $S_4$ with each $L_1, L_2, L_3$ should be located in $\overline{Region_1}$. By symmetry $S_5$ (resp. $S_6, S_7$) intersects with $L_1, L_2, L_3$. This intersection is located in $\overline{Region_2}$ (resp. $\overline{Region_3}, \overline{Region_4}$).

Lemma 6

Each $\overline{Region_i}, i\in [1,4]$ has a non-empty intersection with at least one of $L_1, L_2, L_3$.

Proof

Notice that the bottom-left vertex of $r^*$ is in $\overline{Region_1}$ and the triangle defined by the intersection of $L_1, L_2, L_3$ encloses $r^*$. Suppose that $\overline{Region_1}$ has empty intersection with all $L_1, L_2, L_3$. This implies that the triangle defined by the intersection of $L_1, L_2, L_3$ does not enclose $r^*$, which is a contradiction. Similarly this argument can be applied for $\overline{Region_2}, \overline{Region_3}$ and $\overline{Region_4}$.    $\square$

Lemma 7

At least two of the regions in $\{\overline{Region_i}, i\in [1,4]\}$ do not have an intersection with all three of $L_1, L_2, L_3$.

Proof

Observe that each $L_i, i\in [1,3]$ can intersect with at most three regions of $\{\overline{Region_i}| i\in [1,4]\}$. Thus, we have at most 9 pairs of $(L_i, Region_j)$ when $L_i$ intersects with $Region_j$ for $i\in [1,3], j\in [1,4]$. According to Lemma 6 and the Pigeonhole theorem at least two of the regions in $\{\overline{Region_i}| i\in [1,4]\}$ do not intersect with all three of $L_1, L_2, L_3$.    $\square$

Proof

(Proof of Theorem 3). Lemma 7 implies that the regions corresponding to at least two of the shapes $S_4, S_5, S_6, S_7$ do not intersect with all three of $L_1, L_2, L_3$. This contradicts the fact that the shapes in the set S are pairwise intersecting. Thus, at least one piercing point can be removed from our piercing point set.    $\square$

Algorithm to find the exact location of the piercing points: First, we find the smallest shape, $S_1$, of the set in O(n). Next we apply the Schwarzkopf et al.’s [22] algorithm on $S_1$ to compute the vertices of $r_1 = (w_1, h_1)$ in $O(\log ^2 k)$ time. This allows us to compute the 16 points outlined in Kim’s [16] proof in a constant time. Thus the time complexity of finding 16 piercing points is $O(n + \log ^2 k)$. Next, we can determine in $O(n\log k)$ time which of the 4 corner points can be removed. Thus, we can find 15 piercing points in $O(n\log k + \log ^2 k)$ time.

3.2 Hexagons

In this subsection we determine the piercing number of a set of pairwise intersecting homothets of a regular hexagon. We show that two points are always sufficient and sometimes necessary to pierce such a set. For a hexagon s with an edge parallel to the x-axis, we refer to its edges by Bottom, BottomRight, TopRight, Top, TopLeft, BottomLeft edges. We denote the Bottom edge of s by $s^B$. Respectively we refer to BottomRight, TopRight, Top, TopLeft, BottomLeft edges of s by $s^{BR}, s^{TR}, s^T, s^{TL}, s^{BL}$.

Theorem 4

Any set of pairwise intersecting homothets of a regular hexagon can be pierced by two points.

Proof

(Proof of Theorem 4). Let $C = \{C_0, C_1, \ldots C_{n-1}\}$ be a set of pairwise intersecting homothets of a regular hexagon. Without loss of generality, assume that the bottom edge of every hexagon in C is parallel with the x-axis. Let $TL = \{C_i^{TL} | \forall C_i \in C\}$, and $TR = \{C_i^{TR} | \forall C_i \in C\}$, and $BE = \{C_i^B | \forall C_i \in C\}$. Each element of these sets is a line segment. Segments of each set are associated with the same side of hexagons in C. $\forall C_i^{TL} \in TL$ let $TL_{i}^{+}$ be the halfspace defined by $C_i^{TL}$ that does not contain the corresponding hexagon to $C_i^{TL}$. Let $TL^{+} = \{TL_{0}^{+}, TL_{1}^{+}\ldots , TL_{n-1}^{+}\}$. $\forall C_i^{TR} \in TR$ let $TR_{i}^{+}$ be the halfspace defined by $C_i^{TR}$ that does not contain the corresponding hexagon to $C_i^{TR}$. Let $TR^{+} = \{TR_{0}^{+}, TR_{1}^{+}\ldots , TR_{n-1}^{+}\}$. Let $tl^*$ be the halfspace in $TL^{+}$ that contains all other halfspaces in $TL^{+}$. Such a halfspace exists since all of the halfspaces in $TL^{+}$ are parallel. Let $tr^*$ be the halfspace in $TR^{+}$ that contains all other halfspaces in $TR^{+}$. Such a halfspace exists since all of the halfspaces in $TR^{+}$ are parallel.

Let tl be the corresponding segment in TL to $tl^*$. Let tr be the corresponding segment in TR to $tr^*$. Let be be the top most segment in BE.

Define $L_1$ the line that is parallel to and goes through tl. Similarly, define $R_1$ to be the line that is parallel to and goes through tr, and $B_1$ to be the line that is parallel to and goes through be.

Assume that $L_1, R_1, B_1$ do not intersect at a point p. Otherwise, the two piercing points will be on top of each other at p, thus, p pierces the whole set. Observe that, the intersection points of $L_1, R_1, B_1$ form a equilateral triangle $T_h = ABD$. Let point B be the intersection point of lines $L_1$ and $R_1$. Let point D be the intersection point of lines $L_1$ and $B_1$ and let point A be the intersection point of lines $B_1$ and $R_1$. This triangle can have one of the two following possible shapes.

• Case 1. In the first case, the point B is located above the segment AD. Therefore, the left top side of any hexagon in C is to the left of $L_1$. Similarly, the right top side of any hexagon in C is to the right of $R_1$ and any bottom side of any hexagon in the set is below $B_1$.

• Case 2. In the second case, the point B is located below the segment AD. Therefore, the bottom right side of any hexagon in C is to the right of $L_1$ since, each pair of hexagons have to intersect. The top side of any hexagon in C is above $B_1$ and, the bottom left side of any hexagon is to the left of $R_1$, otherwise it contradicts the fact that each pair of hexagons intersects. Observe that this case is symmetric to the first case. Therefore, giving the proof for the first case is sufficient.

Proof for the case 1: Let $M_L$, $M_R$ and $M_B$ be the mid points corresponding to sides AB, BD and AD of the triangle $T_h = ABD$. We prove that every hexagon in C contains either $M_B$ or B.

Take an arbitrary hexagon s from C. If s contains $M_B$ then we are done. Suppose that s does not contain the point $M_B$. The point $M_B$ can be either to the right of $s^{BR}$ or to the left of $s^{BL}$ and both cases are symmetric. Without loss of generality, assume that the point $M_B$ is to right of the $s^{BR}$. By the definition of $R_1$ the top right edge of any hexagon in C is to the right of $R_1$. Similarly, the bottom edge of any hexagon in C is to the bottom of $B_1$. This implies that the right bottom side of s should cross the lines $B_1$ and $R_1$. Let $i_1$ be the intersection point of $s^{BR}$ and $B_1$, and $i_2$ be the intersection point of $s^{BR}$ and $R_1$.

The point $i_1$ is to the left of $M_B$ and $i_2$ is to the left of $M_R$. Observe that the triangle $i_1i_2D$ is similar to $M_BM_RD$ and $|Di_2| > |DM_B|$. Therefore, the segment $i_1i_2$ is greater than $M_RM_B$. Moreover, the side length of s is greater than or equal to the length of the segment $i_1i_2$, and it is greater than $M_B M_R$ ($|s^B| = |s^{BR}| \ge |i_1i_2| > |M_RM_B| = |M_RB| = |M_BA|$). Considering the facts that the side length of s is greater than $|M_RM_B|$, and $s^{TR}$ is parallel to $R_1$ and to the right of $R_1$. Thus, by convexity of s, $s^{TR}$ crosses $L_1$, and similarly $s^B$ crosses $L_1$. Thus s contains the segment AB and in particular the point B.

   $\square$

4 Conclusion

In this paper we showed that pairwise intersecting convex shapes of fatness $\alpha$ with arbitrary orientation can be pierced by a linear number of points with respect to the fatness parameter of the shapes in the set. The main idea to achieve our results is to avoid covering an area with a grid of high resolution but rather focusing on the perimeter of a specific shape. By using this idea we reduce the number of points sufficient to pierce any pairwise intersecting convex $\alpha$-fat shapes from $O(\alpha ^2)$ to $O(\alpha )$. Our theorem is an improvement over Fredman’s sampling algorithm to find piercing points.

Moreover, for a set of pairwise intersecting homothets we showed that the piercing number is at most 15 points. The piercing number of a set of pairwise intersecting set of homothets of regular hexagons is 2 which is tight. We leave as an open problem to improve our upper bounds.