# The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Boris Aronov, Otfried Cheong, Michael Gene Dobbins, Xavier Goaoc

► To cite this version:

Boris Aronov, Otfried Cheong, Michael Gene Dobbins, Xavier Goaoc. The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions. SoCG 2016, Jun 2016, Boston, United States. pp.10:1-10:16. hal-01393017

HAL Id: hal-01393017

https://hal.science/hal-01393017

Submitted on 5 Nov 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Boris Aronov*¹, Otfried Cheong†², Michael Gene Dobbins‡³, and Xavier Goaoc⁴

1 Department of Computer Science and Engineering, Tandon School of Engineering, New York University, New York, USA

boris.aronov@nyu.edu

2 KAIST, Daejeon, South Korea

otfried@kaist.edu

3 Department of Mathematical Sciences, Binghamton University, Binghamton, USA

mdobbins@binghamton.edu

4 Université Paris Est, LIGM (UMR 8049), Marne la Vallée, France

goaoc@u-pem.fr

## Abstract

We show that the union of *n* translates of a convex body in $\mathbb{R}^3$ can have $\Theta(n^3)$ holes in the worst case, where a *hole* in a set $X$ is a connected component of $\mathbb{R}^3 \setminus X$. This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.

**1998 ACM Subject Classification** I.3.5 Computational Geometry and Object Modeling, F.2.2 Nonnumerical Algorithms and Problems

**Keywords and phrases** Union complexity, Convex sets, Motion planning

**Digital Object Identifier** 10.4230/LIPIcs.SoCG.2016.10

## 1 Introduction

From path planning in robotics [17] to the design of epsilon-nets [7] to analyzing vulnerabilities in networks [1], a variety of combinatorial and algorithmic problems in computational geometry involve understanding the complexity of the union of *n* elementary objects. An abundant literature studies how this union complexity depends on the geometry of the objects, and we refer the interested reader to the survey of Agarwal, Pach and Sharir [2]. In the plane, two important types of conditions were shown to imply near-linear union complexity: restrictions on the number of boundary intersections [18, 12] and fatness [8, 16]. In three dimensions, the former are less relevant as they do not apply to important examples such as motion planning problems. Whether fatness implies low union complexity in $\mathbb{R}^3$ has been identified as an important open problem in the area [14, Problem 4]; to quote Agarwal, Pach and Sharir [2, Section 3.1, §2],

> "A prevailing conjecture is that the maximum complexity of the union of such fat objects is indeed at most nearly quadratic. Such a bound has however proved quite

<figure><img src="image_2.png" /></figure>

<footnote>* B. Aronov is supported by NSF grants CCF-11-17336 and CCF-12-18791.</footnote>

<footnote>† O. Cheong is supported by NRF grant 2011-0030044 (SRC-GAIA) from the government of Korea.</footnote>

<footnote>‡ M. G. Dobbins is supported by NRF grant 2011-0030044 (SRC-GAIA) from the government of Korea.</footnote>
10:2 The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

elusive to obtain for general fat objects, and this has been recognized as one of the
major open problems in computational geometry."

A weaker version of this conjecture asserts that the number of holes in the union of $n$
translates of a fixed convex body in $\mathbb{R}^3$ is at most nearly quadratic in $n$. By a *hole* in a
subset $X \subseteq \mathbb{R}^d$ we mean a connected component of $\mathbb{R}^d \setminus X$. This is indeed a weakening
since the number of holes is a lower bound on the complexity and a family of translates can
be made quite fat by applying a suitable affine transformation. Evidence in support of the
weaker conjecture is that in two dimensions, the union of $n$ translates has at most a linear
number of holes [12], and in three dimensions, the union of $n$ translates of a convex polytope
with $k$ facets has at most $O(kn^2)$ holes [4], so the number of holes grows only quadratically
for any fixed convex polytope.

Remarkably, we refute the conjecture even in this weaker form. We construct a convex body in $\mathbb{R}^3$ that has, for any $n$, a family of $n$ translates with $\Theta(n^3)$ holes in its union. This matches the upper bound for families of arbitrary convex bodies in $\mathbb{R}^3$ [13].

**Theorem 1.** The maximum number of holes in the union of $n$ translates of a compact, convex body in $\mathbb{R}^3$ is $\Theta(n^3)$.

We start with a warm-up example illustrating the idea behind our construction (Section 2).
We then construct a polytope $K_m$, tailored to the value of $m$ considered and with $\Theta(m^2)$ faces;
we give a family of $3m$ translates of $K_m$ (in Section 3) whose union has $\Theta(m^3)$ holes. The final
step of our construction is to turn the family of polytopes ($K_m$) into a limiting “universal”
convex body $K$ that, for any $m$, admits $3m$ translates whose union has $\Theta(m^3)$ holes. We
prove this formally using arguments from algebraic topology, developed in Section 5.

**Further consequences.** We conclude this introduction with two examples of problems in computational geometry whose underlying structure involves a union of translates of a convex body, and on which Theorem 1 casts some new light.

A motion-planning problem asks whether an object, typically in $\mathbb{R}^2$ or $\mathbb{R}^3$, can move from an initial position to a final position by a sequence of elementary motions while remaining disjoint from a set of obstacles (and to compute such a motion when it exists). This amounts to asking whether two given points lie in the same connected component of the *free space*; that is, the set of positions of the object where it intersects no obstacle. When the motions are restricted to translations, the free space can be obtained by taking the complement of the union of the “expansion” (formally: the *Minkowski sum*) of every obstacle by the reflection of the object through the origin. In the simplest case the mobile object is convex, the obstacles consist of $n$ points and the free space is the complement of the union of $n$ translates of a convex body; Theorem 1 implies that already in this case the free space can have large complexity:

**Corollary 2.** There exists a set $P$ of $n$ point obstacles and a convex body $K$ in $\mathbb{R}^3$ such that the free space for moving $K$ by translations while avoiding $P$ has $\Theta(n^3)$ connected components.

The Voronoi diagram of a family $P$ of points $p_1, p_2, \dots, p_n$, called *sites*, in a metric space $X$ is the partition of $X$ according to the closest $p_i$. A subset $Q \subseteq P$ defines a *face* of the diagram if there exist some point $x \in X$ at equal distance from all sites of $Q$, and strictly further away from all sites in $P \setminus Q$. A case of interest is when $X$ is $\mathbb{R}^d$ equipped with a *convex distance function* $d_U$ defined by a convex unit ball $U$ (in general, $d_U$ is not a metric, as $U$ needs not be centrally symmetric). A *face* of the Voronoi diagram with respect to $d_U$ is
defined to be a connected component of the set {$x : d(x, q) \le d(x, p)$, for all $q \in Q, p \in P$} for some $Q \subset P$ defining a face; the complexity of a Voronoi diagram is measured by the number of its faces of all dimensions. In $\mathbb{R}^2$, the complexity of the Voronoi diagram of $n$ point sites with respect to $d_U$ is $O(n)$, independent of the choice of $U$ [5, 9].

The state of knowledge is less satisfactory in three dimensions where we know near-quadratic complexity bounds for the Voronoi diagram with respect to $d_U$ if $U$ is a constant complexity polytope [19], and that by making $U$ sufficiently complicated one can have four point sites define arbitrarily many Voronoi vertices (that is, isolated points at equal distance from these four sites) [11]. If we grow equal-radii balls (for $d_U$) centered in each of the $p_i$ simultaneously, every hole in the union of these balls must contain a Voronoi vertex. Theorem 1 therefore implies that one can also find $\Omega(n^3)$ different quadruples of point sites defining Voronoi vertices.

**Corollary 3.** There exist a convex distance function $d_U$ and a set $P$ of $n$ points in $\mathbb{R}^3$ such that $\Omega(n^3)$ different quadruples of $P$ define a Voronoi vertex in the Voronoi diagram of $P$ with respect to $d_U$.

**Notation.** For an integer $n$ we let $[n]$ denote the set $\{1, \dots, n\}$. If $A$ and $B$ are two subsets of $\mathbb{R}^d$ we denote by $A+B$ their Minkowski sum

$$A+B = \{a+b : a \in A, b \in B\}$$

and by $\text{conv}(A)$ the convex hull of $A$. We refer to coordinates in three space by $x, y, z$. We refer to the positive $z$-direction as “upward,” and to the positive $y$-direction as “forward.” For an object $A \subset \mathbb{R}^3$, the “front” boundary of $A$ is the upper $y$-envelope. Similarly, the “back” boundary is the lower $y$-envelope.

**Remark on figures.** The reader should take heed that in several places we give explicit coordinates for a construction and provide a figure, where the figure depicts the qualitative geometric features of interest using different coordinates. Using the coordinates chosen for convenience of computation would have resulted in figures where features are too small to see.

## 2 Many holes touching a single facet

We first introduce the key idea of our constructions with a simpler goal: constructing $2m+1$ translates of a convex polytope with $\Omega(m^2)$ holes in the union, all incident to a common facet.

Let $K$ be the polytope depicted in Figure 1, the convex hull of the following seven points:

$$a = (0, 0, 0), b = (1, 0, 0), c = (0, 0, -1), d = (1, 0, -1),$$

$$e = (1/2, 1/2, 1/2), f = (0, 1, 0), \text{ and } g = (1, 1, 0).$$

We fix an integer $m > 0$ and let $C = K$ be the trivial translate of $K$. Let $F$ denote the facet of $C$ with vertices $a, b, c, d$. We then pick $m$ translates of $K$, denoted $B_1, B_2, \dots, B_m$, whose top-most vertices (corresponding to vertex $e$) are placed regularly along the edge $ab$ of $F$. The top part of the intersection $B_j \cap F$ is a triangular region, shown in blue in Figure 1 (bottom). The union $\cup_{j=1}^m B_j$ bounds $m-1$ regions below the edge $ab$ of $F$. Let $\ell$ denote the height of one such region; that is the distance between $B_1 \cap B_2$ and the edge $ab$ of $F$. Let $c'$ denote the point on the segment $ac$ of $F$ at distance $\ell$ from $a$ (see again
<figure><img src="image_3.png" /><figcaption>■ **Figure 1** Top left: The convex polytope $K$ for the construction of Section 2; Top right: three important $(x, z)$ cross-sections of $K$. The cross section in the back (green) is the facet $F$ that touches many holes, the one in the center (blue) is used to produce vertical cones, and the one in the front (red) is used to produce horizontal edges. Bottom: The grid formed on the facet $F$ by horizontal segments and vertical cones.</figcaption></figure>

Figure 1 (bottom)). We next pick $m$ translates of $K$, denoted $A_1, A_2, \dots, A_m$, whose vertices corresponding to $f$ are placed regularly along the segment $ac'$.

The intersections $F \cap B_j$ and $F \cap A_i$, for $i,j \in [m]$, form a grid in $F$ with $m(m-1)$ holes on $F$. Since two consecutive $A_i$ leave only a narrow tunnel incident to $F$, and each $B_j$ entirely cuts this tunnel, each of the holes on $F$ is indeed on the boundary of a distinct hole in the union of all translates in $\mathbb{R}^3$.

► **Claim 4.** The union $\cup_{i=1}^m A_i \cup \cup_{j=1}^m B_j \cup C$ has $\Omega(m^2)$ holes, all touching the facet $F$ of $C$.

Since this is only a warm-up example, we do not include a formal proof of the claim.

3 The construction of $K_m$

The construction of Section 2 uses three features of $K$: a portion of a cone with apex $e$, a portion of a prism with edge $fg$, and a facet $F$. We combined the $A_i$'s and the $B_j$'s in a grid-like structure that created $\Theta(m^2)$ local minima in the $y$-direction on the front boundary of the union $\cup A_i \cup \cup B_j$. Each of these minima is the bottom of a “pit”, and $C$ acts as a “lid” to turn each pit into a separate hole. The construction we use to prove Theorem 1 is based on a similar principle, but before giving this construction, we first fix a value $m > 0$, and then build a convex polytope $K_m$ depending on $m$ and a family of $3m$ translates with $\Theta(m^3)$ holes. The construction of $K_m$ consists of two parts, which we refer to as FRONT and BACK.

**The auxiliary paths.** To construct our polytope $K_m$ we use two auxiliary polygonal paths $\eta$ and $\gamma$. They both start at the origin $0$. The path $\eta$ has $m$ edges, lies in the $(y, z)$-plane, and
<figure><img src="image_4.png" /><figcaption>Figure 2 The union of the translates $B_1, B_2, \dots, B_m$ (left) and $A_1, A_2, \dots, A_m$ (right). The spacing between the translates is exaggerated for clarity.</figcaption></figure>

is convex<fnref n="1" /> in both directions $(0, -1, 0)$ and $(0, 0, -1)$. The path $\gamma$ has $m+2$ edges, lies in the $(x, y)$-plane, and is convex in direction $(0, -1, 0)$. We denote the $j$th vertex of $\eta$ by $w_{j,0}$ and the $k$th vertex of $\gamma$ by $w_{0,k}$, see the top left of Figure 3.

**The front part.** We define a “grid” of $(m+1) \times (m+3)$ points, which are the vertices of the polyhedral surface $\eta + \gamma$ (see the top right of Figure 3), by putting

$$w_{j,k} = w_{j,0} + w_{0,k} \quad \text{for } j \in \{0, 1, \dots, m\} \text{ and } k \in \{0, 1, \dots, m+2\}.$$

We then add a point $v_{j,k}$ on the edge $w_{j,k}w_{j,k+1}$ as follows (see the bottom left of Figure 3):

$$v_{j,k} = \left(1 - \frac{j}{m+1}\right) w_{j,k} + \frac{j}{m+1} w_{j,k+1} \quad \text{for } j \in \{0, 1, \dots, m\} \text{ and } k \in \{0, 1, \dots, m+1\}.$$

For $j \in \{0, \dots, m\}$ we define two polygonal paths

$$\gamma_j = w_{j,0} + \gamma = w_{j,0}w_{j,1}w_{j,2}\dots w_{j,m+1}w_{j,m+2} \text{ and}$$

$$\xi_j = w_{j,0}v_{j,0}v_{j,1}v_{j,2}v_{j,3}\dots v_{j,m}v_{j,m+1}w_{j,m+2}.$$

Note that $\xi_0 = \gamma_0 = \gamma$, that the paths $\gamma_j$ are simply translates of $\gamma$, and that the path $\xi_j$ lies entirely in the convex region $\gamma_j + (0, \mathbb{R}^-, 0)$ and the vertices of $\xi_j$ lie on $\gamma_j$; see Figure 4.

The front part $\text{FRONT}$ of $K_m$ is the convex hull of the paths $\xi_j$ (see the bottom right of Figure 3):

$$\text{FRONT} = \text{conv} (\xi_0 \cup \xi_1 \cup \dots \cup \xi_m).$$

Observe that the paths $\eta$ and $\gamma$ can be chosen so that, for each $j \in [m]$, the path $\xi_j$ lies entirely on the front boundary as well as on the upper boundary of $\text{FRONT}$.

Let $E_{j,k}$ denote the edge $w_{j,k}w_{j,k+1}$ and let $E_k = E_{0,k}$. Consider the point $v_{j,k}$ on $E_{j,k}$. Since $\xi_j$ lies entirely on the upper boundary of $\text{FRONT}$, no part of $\text{FRONT}$ appears above $E_{j,k}$, and since $v_{j,k}$ is the only point where the segment $E_{j,k}$ intersects $\text{FRONT}$ for $j, k \in [m]$, the vertical plane containing $E_{j,k}$ intersects $\text{FRONT}$ in a downward extending cone with apex $v_{j,k}$; see Figure 5. Note that this fails for $k = 0$ and for $k = m+1$.

<footnote n="1">¹ We say a path $\pi$ is convex in a direction $u$ if the orthogonal projection of $\pi$ onto $u^\perp$ is injective and the set $\pi + \mathbb{R}^+u$ is convex.</footnote>
10:6 The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

<figure><img src="image_5.png" /><figcaption>■ **Figure 3** Design of FRONT. Top left: The auxiliary paths $\eta$ and $\gamma$. Top right: The surface $\eta + \gamma$ defining the “grid” of vertices $w_{j,k}$. Bottom left: The points $v_{j,k}$. Bottom right: The front boundary of FRONT.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>■ **Figure 4** View of the paths $\xi_j$ from above (with the paths $\gamma_j$ represented in grey).</figcaption></figure>

**The back part.** We now define two vectors, $u_1 = w_{m,m+2} - (0, t, 0)$, where $t$ is some positive real number, and $u_0$, the orthogonal projection of $u_1$ on the $(x, y)$-plane. We define BACK as the Minkowski sum of the segment $u_0u_1$ and $-\gamma$, the reflection of $\gamma$ with respect to the origin (see Figure 6). The value of $t$ is adjusted so that FRONT and BACK have disjoint convex hulls.

By construction, BACK consists of $m+2$ rectangles orthogonal to the $(x, y)$-plane, namely the rectangles $u_0u_1 - E_k$, for $k \in \{0, \dots, m+1\}$. The top and bottom edges of each rectangle are $u_1 - E_k$ and $u_0 - E_k$ respectively.

**The polytope $K_m$ and its translates.** We now let $K_m = \text{conv}(\text{FRONT} \cup \text{BACK})$, see Figure 7, and define three families of its translates. First, for $k \in [m]$, we define a translate $C_k$ such that the edge $u_1 - E_k$ of $C_k$ coincides with the edge $E_k$ of $K_m$. Formally, we have

$$C_k = K_m + c_k, \quad \text{where} \quad c_k = w_{0,k} - (u_1 - w_{0,k+1}).$$

See Figure 8 (right). The vertical facet formed by $u_1 - E_k$ and $u_0 - E_k$ of $C_k$ will be incident to a quadratic number of holes, playing the same role as the facet $F$ in the previous section.
<figure><img src="image_7.png" /><figcaption>Figure 5 Intersection of vertical panels through the path $\gamma_1$ with FRONT.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 6 Design of BACK.</figcaption></figure>

Let us denote this facet as $R_k$.

Next, for $j \in [m]$, we define a translate $B_j$ of $K_m$ as follows:

$$B_j = K_m + b_j, \quad \text{where} \quad b_j = -w_{j,0}.$$

In other words, the path $\xi_j$ of $B_j$ lies in the $(x, y)$-plane and the vertex $v_{j,k}$ of $B_j$ lies on $E_k$. See Figure 8 (middle).

Consider now the edge $E_k$, for $k \in [m]$. For each $j \in [m]$, the edge $E_k$ contains the vertex $v_{j,k}$ of $B_j$. By the argument above, the intersection of $B_j$ with the facet $R_k$ is a vertical cone with apex $(1 - j/m+1)w_{0,k} + (j/m+1)w_{0,k+1}$. These apices are regularly spaced along $E_k$, and we obtain a configuration similar to Figure 1. In other words, the union $\cup_{j \in [m]} B_j$ bounds $m-1$ triangular regions below the edge $E_k$ on the facet $R_k$ of $C_k$.

We now pick a sufficiently small number $\varepsilon > 0$ and define our final family of translates. For $i \in [m]$, let

$$A_i = K_m + a_i, \quad \text{where} \quad a_i = (0, 0, -\frac{i}{m}\varepsilon).$$

The translates $A_i$ are defined by translating $K_m$ vertically such that for every $i \in [m]$ and $k \in [m]$, the edge $E_k$ of $A_i$ appears as a horizontal edge on $R_k$, cutting each of the $m-1$ triangular regions. See Figure 8 (left).

**The family $\mathcal{F}$**. We now finally set $\mathcal{F} = \{A_1, \dots, A_m, B_1, \dots, B_m, C_1, \dots, C_m\}$. The union of the family $\mathcal{F}$ has at least $m^2(m-1)$ holes: For $k \in [m]$, we consider the facet $R_k$ of $C_k$. On this facet, the union of the $B_j$ and $A_i$ forms a grid with $m(m-1)$ holes. As in Section 2, we argue that each of these holes is incident to a distinct component of the complement of the union of all the translates.
<figure><img src="image_9.png" /><figcaption>■ **Figure 7 Left:** The polytope $K_m$. **Right:** $K_m$ as viewed from behind.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>■ **Figure 8** *Top from left:* A translate $A_i$, $B_j$, and $C_k$. *Bottom from left:* The intersection of the respective translates $A_i$, $B_j$, and $C_k$ above with the facets $R_1, \dots, R_m$.</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Figure 9 A convex body K, not depending on n, with translates forming Θ(n³) holes.</figcaption></figure>

We will not give a formal proof of this fact, since we will give an even stronger construction in Section 4, and we will include a formal, algebraic argument for the correctness of that construction.

**Explicit coordinates for $K_m$.** The reader not satisfied with the qualitative description of $\mathcal{F}$ may enjoy verifying that the following coordinates satisfy the properties we needed for our construction:

$$w_{j,0} = (0, -3j, 1 - 2^{-j})$$

$$w_{0,k} = (\cos \theta_k - 1, \sin \theta_k, 0)$$

$$w_{0,m+2} = (-2, 0, 0),$$

$$u_1 = (-2, -3m - 3, 1 - 2^{-m}),$$

$$u_0 = (-2, -3m - 3, 0).$$

for $0 \le j \le m,$

for $\theta_k = \frac{\pi}{3} \left( \frac{k-1}{m} + 1 \right), 1 \le k \le m + 1,$

## 4 Constructing a universal convex body

The family of translates constructed in Section 3 uses a convex polytope $K_m$ that depends on $m$. In this section we construct a single convex body $K$ that allows the formation of families of $n$ translates of $K$, for arbitrarily large $n$, with a cubic number of holes. (Note that the *position* of the translates in the family will depend on $n$.)

**The convex body K.** The finite polygonal paths $\gamma$ and $\eta$ are replaced by infinite polygonal paths. We must also redefine the vertices $v_{j,k}$, but the rest of the construction remains largely the same as before. (Figure 9 illustrates the construction.)
10:10 The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Using $\zeta_s = \sum_{t=1}^{\infty} t^{-s}$ for $s \in \{2, 3\}$, we define vertices as follows:

$$w_{0,0} = 0,$$
$$w_{j,0} = w_{j-1,0} + (0, -j^{-2}, j^{-3}) \quad \text{for } j \in \{1, 2, \dots\},$$

$$w_{\infty,0} = \lim_{j \to \infty} w_{j,0} = (0, -\zeta_2, \zeta_3),$$
$$w_{0,k} = w_{0,k-1} + (k^{-2}, k^{-3}, 0) \quad \text{for } k \in \{1, 2, \dots\},$$

$$w_{0,\infty} = \lim_{k \to \infty} w_{0,k} = (\zeta_2, \zeta_3, 0),$$
$$w_{j,k} = w_{j,0} + w_{0,k} \quad \text{for } j, k \in \{1, 2, \dots, \infty\},$$

$$v_{j,k} = \frac{1}{(j+1)^3} w_{j,k} + \frac{(j+1)^3 - 1}{(j+1)^3} w_{j,k+1} \quad \text{for } j, k \in \{0, 1, \dots\},$$

$$u_1 = (\zeta_2, -2, \zeta_3),$$

$$u_0 = (\zeta_2, -2, 0).$$

We define the convex paths $\gamma$ as $w_{0,0}w_{0,1}w_{0,2}\dots w_{0,\infty}$, and $\eta$ as $w_{0,0}w_{1,0}w_{2,0}\dots w_{\infty,0}$. Again we let $E_k$ denote the edge $w_{0,k}w_{0,k+1}$, for $k \in \{0, 1, \dots\}$. The vertex $v_{j,k}$ lies on the edge $w_{j,k}w_{j,k+1} = E_k + w_{j,0}$. For $j \in \{1, 2, \dots\}$, we set $\gamma_j = w_{j,0} + \gamma$, and define the convex path $\xi_j$ as $w_{j,0}v_{j,0}v_{j,1}v_{j,2}v_{j,3}\dots w_{j,\infty}$; note that $\xi_0 = \gamma$. The path $\xi_\infty$ is equal to $\gamma_\infty = \gamma + w_{\infty,0}$; note that $\lim_{j \to \infty} v_{j,k} = w_{\infty,k+1}$.

The front part of $K$ is the convex hull of the paths $\xi_j$:

$$\text{FRONT} = \text{conv}(\xi_0 \cup \xi_1 \cup \xi_2 \cup \dots \cup \xi_\infty).$$

The back part BACK of $K$ is the Minkowski sum of $u_1u_0$ and $-\gamma$. By construction, it is the union of the rectangles $u_1u_0 - E_k$, for $k \in \{0, 1, 2, \dots\}$. The top and bottom edges of each rectangle are $u_1 - E_k$ and $u_0 - E_k$.

Finally, we define $K = \text{conv}(\text{FRONT} \cup \text{BACK})$, concluding the description of our convex body $K$. This body has the following property.

**► Lemma 5.** The polygonal path $\xi_j$ lies entirely on the front boundary of $K$.

**Proof.** We will show that any point in $\xi_j$ lies outside the convex hull of the regions $\xi_{j'} + (0, \mathbb{R}^-, 0)$, for $j' \neq j$. Fix $j \in \mathbb{N}$, and let $\Gamma$ be the convex hull of the regions $\gamma_{j'} + (0, \mathbb{R}^-, 0)$, for $j' \neq j$. Since the path $\xi_{j'}$ lies in the convex region $\gamma_{j'} + (0, \mathbb{R}^-, 0)$, it suffices to show that $\xi_j$ lies outside $\Gamma$. Since the $\gamma_j$ are just translates of $\gamma$, the body $\Gamma$ is easy to describe. In particular, between the $(x, y)$-parallel planes containing $\gamma_{j-1}$ and $\gamma_{j+1}$, its front boundary is formed by rectangles that are the convex hull of $E_k + w_{j-1,0}$ and $E_k + w_{j+1,0}$. Let $\Pi$ be the $(x, y)$-parallel plane containing $\xi_j$ and $\gamma_j$. The front boundary of $\Gamma \cap \Pi$ is again a translate of $\gamma$. We first compute this translate of $\gamma$, by finding the intersection point $p$ of the segment $w_{j-1,0}w_{j+1,0}$ with $\Pi$.

Let $p' = p - w_{j-1,0}$. This makes $p'$ the point at height $1/j^3$ on the line through the origin and the point $w_{j+1,0} - w_{j-1,0}$. Since

$$w_{j+1,0} - w_{j-1,0} = \left(0, -\frac{1}{j^2} - \frac{1}{(j+1)^2}, \frac{1}{j^3} + \frac{1}{(j+1)^3}\right) = \left(0, \frac{-j^2 - (j+1)^2}{j^2(j+1)^2}, \frac{j^3 + (j+1)^3}{j^3(j+1)^3}\right),$$

this gives

$$p' = \left(0, \frac{-(j+1)(j^2 + (j+1)^2)}{j^2(j^3 + (j+1)^3)}, \frac{1}{j^3}\right).$$
Since $p = p' + w_{j-1,0}$ and $w_{j,0} - w_{j-1,0} = (0, -j^{-2}, j^{-3})$, we have

$$p = w_{j,0} - \left(0, \frac{1}{j^3 + (j+1)^3}, 0\right).$$

We have just computed the front boundary $\gamma + p$ of $\Gamma \cap \Pi$, and we want to show that the path $\xi_j$ lies farther in front of this boundary. Since $\gamma + p$ and $\xi_j$ are convex paths, it suffices to show that any vertex of $\gamma + p$ lies behind $\xi_j$. These vertices are the points $w_{0,k} + p$, for $k \in \{0, 1, 2, \dots\}$. That is, we will show $w_{0,k} + p \in \xi_j + (0, \mathbb{R}^-, 0)$.

We fix some $k \in \{1, 2, \dots\}$ and consider $w_{0,k} + p$. The line parallel to the y-axis through $w_{0,k} + p$ intersects the edge $v_{j,k-1}v_{j,k}$ of $\xi_j$ in a point $q$. We need to show that $q^y \ge (w_{0,k} + p)^y$ (here and in the following, we use superscripts $x, y, z$ to denote the coordinates of a point).

It will be convenient to translate our coordinate system such that $w_{j,k}$ is the origin. This means that $\Pi$ is the plane $z = 0$. Letting $J = (j+1)^3$, we have:

$$\begin{align*}
w_{0,k} + p - w_{j,k} &= w_{0,k} + p - (w_{j,0} + w_{0,k}) = \left(0, \frac{-1}{j^3 + J}, 0\right), \\
v_{j,k} - w_{j,k} &= \frac{1-J}{J}w_{j,k} + \frac{J-1}{J}w_{j,k-1} = \frac{J-1}{J}[w_{j,k+1} - w_{j,k}], \\
v_{j,k-1} - w_{j,k} &= \frac{1}{J}w_{j,k-1} - \frac{1}{J}w_{j,k} = \frac{1}{J}[w_{j,k-1} - w_{j,k}].
\end{align*}$$

Now parameterize the segment $v_{j,k-1}v_{j,k}$ as $E(s)$, for $0 \le s \le 1$, using our new coordinate system:

$$E(s) = (1-s) \frac{J-1}{J} [w_{j,k+1} - w_{j,k}] + \frac{s}{J} [w_{j,k-1} - w_{j,k}].$$

The x- and y-coordinates of the point $E(s)$ are

$$E(s)^x = (1-s) \frac{J-1}{J} \frac{1}{(k+1)^2} - \frac{s}{J} \frac{1}{k^2}, \quad E(s)^y = (1-s) \frac{J-1}{J} \frac{1}{(k+1)^3} - \frac{s}{J} \frac{1}{k^3}.$$

We have $q - w_{j,k} = E(t)$, for the $t \in [0, 1]$ where $E(t)^x = 0$. This condition is equivalent to $(1-t)(J-1)k^2 = t(k+1)^2$, and therefore

$$t = \frac{(J-1)k^2}{(k+1)^2 + (J-1)k^2}, \\ E(t)^y = \frac{1-J}{J} \frac{1}{k(k+1)((k+1)^2 + (J-1)k^2)} \ge \frac{1-J}{J} \frac{1}{2(J+3)},$$

where we used $k(k+1) \ge 2$, $k^2 \ge 1$, $(k+1)^2 - k^2 \ge 3$, and the fact that $1 - J \le 0$. We further have

$$(w_{0,k} + p - w_{j,k})^y = \frac{-1}{j^3 + J} < \frac{-1}{2J} < \frac{1 - J}{2J(J + 3)} \le E(t)^y = (q - w_{j,k})^y,$$

and therefore $(w_{0,k} + p)^y < q^y$. Thus, $w_{0,k} + p \in \xi_j + (0, \mathbb{R}^-, 0)$, so $\xi_j$ is in front of $\Gamma$ and as such is on the front boundary of $K$. ◀

**The translates.** We now pick a number $m \in \mathbb{N}$ and construct a family $\mathcal{F}$ of $3m$ translates of $K$ such that their union will have a cubic number of holes. This construction is identical to the construction in Section 3:

First, for $k \in [m]$, we define a translate $C_k$ such that the edge $u_1 - E_k$ of $C_k$ coincides with the edge $E_k$ of $K$, that is

$$C_k = K + c_k, \quad \text{where } c_k = w_{0,k} - (u_1 - w_{0,k+1}).$$
10:12 The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Again we denote the vertical facet formed by $u_1 - E_k$ and $u_0 - E_k$ of $C_k$ as $R_k$.

Next, for $j \in [m]$, we define a translate $B_j$ of $K$ as follows:

$$B_j = K + b_j, \quad \text{where} \quad b_j = -w_{j,0}.$$

In other words, the path $\xi_j$ of $B_j$ lies in the $(x, y)$-plane, the vertex $v_{j,k}$ of $B_j$ lies on $E_k$.

For the third group of translates we need to determine a sufficiently small $\varepsilon > 0$. First, observe that the points $w_{j,k}$, for $j, k \in [m]$, do not lie on $K$. Let $\varepsilon_1 > 0$ be smaller than the distance of $w_{j,k}$ to $K$, for all $j, k \in [m]$. Second, consider the $m^2$ points $v_{j,k} + b_j$ for $j, k \in [m]$ on the path $\gamma$. Let $\varepsilon_2$ be the shortest distance between any two of these points.

Consider now the segment $w_{j,k}w_{j,k+1}$, for some $j, k \in [m]$. It touches $K$ in the point $v_{j,k}$, the rest of the segment lies entirely outside $K$. This implies that there is an $\varepsilon_{j,k} > 0$ such that any line parallel to $w_{j,k}w_{j,k+1}$ at distance less than $\varepsilon_{j,k}$ intersects $K$ only within a neighborhood of $v_{j,k}$ of radius $\varepsilon_2/3$.

We choose $\varepsilon < \varepsilon_1$ and $\varepsilon < \varepsilon_{j,k}$, for all $j, k \in [m]$. With this choice of $\varepsilon > 0$, we can finally define, for $i \in [m]$:

$$A_i = K + a_i, \quad \text{where} \quad a_i = (0, 0, -\frac{i}{m}\varepsilon).$$

Our family $\mathcal{F}$ is

$$\mathcal{F} = \{A_1, \dots, A_m, B_1, \dots, B_m, C_1, \dots, C_m\}.$$

**The nerve.** To every family $\mathcal{X} = \{X_1, X_2, \dots, X_n\}$ of $n$ sets is associated a collection of subfamilies $\mathcal{N}(\mathcal{X})$, called the *nerve of $\mathcal{X}$*, defined as follows:

$$\mathcal{N}(\mathcal{X}) = \left\{ \mathcal{Y} \subseteq \mathcal{X} : \bigcap_{X \in \mathcal{Y}} X \neq \emptyset \right\}.$$

In a sense, the nerve is a natural generalization of the *intersection graph*. In Section 5, we will count the number of holes in the union of $\mathcal{F}$ by computing the rank of certain matrices defined in terms of its nerve. We now give an explicit description of the nerve of the family $\mathcal{F}$. Consider the following subfamilies of $\mathcal{F}$:

$$\Delta_1 = \{A_1, \dots, A_m, B_1, \dots, B_m\},$$

$$\Delta_2 = \{B_1, \dots, B_m, C_1, \dots, C_m\},$$

$$\Delta_{i,k} = \{A_i, C_k, C_{k+1}\} \quad \text{for } (i,k) \in [m] \times [m-1],$$

$$\Delta_{i,j,k} = \{A_i, B_j, C_k\} \quad \text{for } (i,j,k) \in [m]^3.$$

**► Lemma 6.** The set of inclusion-maximal subfamilies in $\mathcal{N}(\mathcal{F})$ is

$$\mathcal{M} = \{\Delta_1, \Delta_2\} \cup \{\Delta_{i,k} : (i,k) \in [m] \times [m-1]\} \cup \{\Delta_{i,j,k} : (i,j,k) \in [m]^3\}.$$

**Proof.** To check that the subfamilies in $\mathcal{M}$ are in $\mathcal{N}(\mathcal{F})$, we find a point in the intersection of each of them. Specifically, we argue that

$$w_{0,k+1} + a_i \in A_i \cap C_k \cap C_{k+1},$$

$$v_{j,k} + a_i + b_j \in A_i \cap B_j \cap C_k,$$

$$(0, -1, 0) \in \bigcap \{A_1, \dots, A_m, B_1, \dots, B_m\},$$

$$(\zeta_2, 2, -1) \in \bigcap \{B_1, \dots, B_m, C_1, \dots, C_m\},$$
see the full version [3, Appendix A] Now, let $\sigma$ be a maximal subfamily in $\mathcal{N}(\mathcal{F})$. If $\sigma$ does not contain any $C_k$ then $\sigma \subseteq \Delta_1$ and by maximality $\sigma = \Delta_1$. Similarly, if $\sigma$ does not contain any $A_i$ then $\sigma \subseteq \Delta_2$ and by maximality $\sigma = \Delta_2$.

We can therefore assume that $A_i, C_k \in \sigma$. By definition of $K$ and $\mathcal{F}$ we have $A_i \cap C_k = E_k + a_i$. Since $A_i \cap C_k$ and $A_{i'} \cap C_k$ are parallel segments for $i' \neq i$, $\sigma$ cannot contain $A_{i'}$.

Assume now that $\sigma$ contains no $B_j$. The segments $E_k$ and $E_{k'}$ intersect if and only if $k$ and $k'$ differ by one. It follows that $\sigma$ is either $\Delta_{i,k}$ or $\Delta_{i,k-1}$.

In the final case, $\sigma$ contains some $B_j$, for $j \in [m]$. The segment $E_k + a_i - b_j$ is parallel to $w_{j,k}w_{j,k+1}$ at distance at most $\varepsilon < \varepsilon_{j,k}$, and so it intersects $K$ only in a neighborhood of $v_{j,k}$ of radius at most $\varepsilon_2/3$. It follows that $E_k + a_i$ intersects $B_j = K + b_j$ only in a neighborhood of the same radius around the point $v_{j,k} + b_j$. But, the shortest distance between these points is $\varepsilon_2$, and so these neighborhoods are disjoint. It follows that $\sigma$ contains no other $B_{j'}$, for $j' \neq j$.

Since the point $w_{0,k} + a_i$ lies at distance at most $\varepsilon$ from $w_{0,k}$, but the point $w_{j,k} = w_{0,k} - b_j$ has distance larger than $\varepsilon_1 > \varepsilon$ from $K$, we have $A_i \cap C_{k-1} \cap C_k = w_{0,k} + a_i \notin B_j$, and so $C_{k-1} \notin \sigma$. For the same reason $C_{k+1} \notin \sigma$. It follows that $\sigma = \{A_i, C_k, B_j\} = \Delta_{i,j,k}$. $\quad$

## 5 Counting holes in the union via the nerve

In this section we use homology to count the number of holes in a union of convex objects and prove Theorem 1; we first illustrate our arguments by giving a new proof of Kovalev's upper bound [13]. We start by recalling some standard topological machinery.

**Homology and Betti numbers.** An abstract simplicial complex $\Delta$ with vertex set $V$ is a set of subsets of $V$ closed under taking subsets: if $\sigma \in \Delta$ and $\tau \subseteq \sigma$ then $\tau \in \Delta$. An element $\sigma \in \Delta$ is called a *simplex*; the *dimension* of a simplex is its cardinality minus 1, so singletons are simplices of dimension 0, pairs are simplices of dimension 1, etc. A simplex of dimension $i$ is called an $i$-simplex for short. The *vertices* of a simplex $\sigma \in \Delta$ are the singletons contained in $\sigma$. Note that the nerve of a family of convex sets is an abstract simplicial complex.

Let $\Delta$ be an abstract simplicial complex on a totally ordered vertex set $V$. The $i$th real chain space of $\Delta$, denoted $C_i(\Delta)$, is the real vector space spanned$^2$ by the $i$-simplices of $\Delta$. For $i \in \mathbb{N}$, the $i$th boundary map $\partial_i : C_i(\Delta) \to C_{i-1}(\Delta)$ is the linear map defined on a basis of $C_i(\Delta)$ as follows. For any $i$-simplex $\sigma = \{v_0, v_1, \dots, v_i\} \in \Delta$ with $v_0 < v_1 < \dots < v_i$,

$$ \partial_i(\sigma) = \sum_{j=0}^{i} (-1)^j (\sigma \setminus \{v_j\}). $$

That is, $\partial_i$ maps every $i$-dimensional simplex to an element of $C_{i-1}(\Delta)$, namely an alternating sum of its facets. Observe that $\partial_i \circ \partial_{i+1} = 0$, so that $\mathrm{im} \partial_{i+1} \subseteq \ker \partial_i$. The $i$th simplicial homology group $H_i(\Delta, \mathbb{R})$ of $\Delta$ is defined as the quotient $\ker \partial_i / \mathrm{im} \partial_{i+1}$ and the $i$th Betti number $\beta_i(\Delta)$ of $\Delta$ is the dimension of $H_i(\Delta, \mathbb{R})$, hence:

$$ \beta_i(S) = \dim \ker \partial_i - \rank \partial_{i+1}. \quad (1) $$

If $X$ is a subset of $\mathbb{R}^d$, one can define, in a similar but more technical way, the singular homology groups of $X$ and its Betti numbers. We do not recall those definitions (the interested reader is referred to [10, 15]) but emphasize two facts that will be useful:

<footnote>$^2$ In other words, the $i$-dimensional simplices of $\Delta$ form a basis of the vector space $C_i(\Delta)$, which consists of formal sums of $i$-simplices, each simplex being assigned a real coefficient.</footnote>
10:14 The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

(i) $\beta_0(X)$ is the number of connected components of $X$, assuming $X$ admits a cell decomposition.

(ii) If $\mathcal{X} = \{X_1, X_2, \dots, X_n\}$ is a family of convex objects in $\mathbb{R}^d$ and $U = \bigcup_{i=1}^n X_i$ then $H_i(U, \mathbb{R}) \simeq H_i(\mathcal{N}(\mathcal{X}))$; as a consequence, $U$ and $\mathcal{N}(\mathcal{X})$ have the same Betti numbers. This follows from the classical Nerve Theorem of Borsuk [6].

**Counting holes.** We can now relate the number of holes in the union of a family of convex objects to one particular Betti number of its nerve.

**Lemma 7.** If $\mathcal{X} = \{X_1, X_2, \dots, X_n\}$ is a family of compact convex objects in $\mathbb{R}^d$ then the number of holes of $U = \bigcup_{i=1}^n X_i$ is $\beta_{d-1}(\mathcal{N}(\mathcal{X})) + 1$.

**Proof.** The number of holes of $U$ is, by definition, the number of connected components of $\mathbb{R}^d \setminus U$, which is $\beta_0(\mathbb{R}^d \setminus U)$. Assume $d > 1$. For any compact locally contractible subset $T \subseteq \mathbb{S}^d$, Alexander duality gives $\beta_{d-1}(T) = \beta_0(\mathbb{S}^d \setminus T) - 1$. Identifying the $d$-sphere with the one-point compactification of $d$-space, $\mathbb{S}^d \simeq \mathbb{R}^d \cup \{\infty\}$, we have that

$$ \beta_0(\mathbb{R}^d \setminus U) = \beta_0(\mathbb{S}^d \setminus U) = \beta_{d-1}(U) + 1, $$

and by the Nerve Theorem, $\beta_{d-1}(U) = \beta_{d-1}(\mathcal{N}(\mathcal{X}))$.

<figure><img src="image_12.png" /></figure>

As an illustration let us see how a version of the upper bound of Kovalev [13] for compact convex objects immediately follows from Lemma 7:

**Corollary 8.** The number of holes in the union of $n$ compact convex objects in $\mathbb{R}^d$ is at most $\binom{n}{d} + 1$.

**Proof.** Let $\mathcal{X}$ be a family of $n$ compact convex objects in $\mathbb{R}^d$. By Lemma 7, the number of holes of the union of the members of $\mathcal{X}$ is $\beta_{d-1}(\mathcal{N}(\mathcal{X})) + 1$. Let $\partial_i$ denote the $i$th boundary operator of $\mathcal{N}(\mathcal{X})$. By definition, $\beta_{d-1}$ is the dimension of the quotient of the vector space ker $\partial_{d-1}$ by the vector space im $\partial_d$. Now, ker $\partial_{d-1}$ is contained in the space $C_{d-1}(\mathcal{N}(\mathcal{X}))$ spanned by the $(d-1)$-simplices of $\mathcal{N}(\mathcal{X})$; since $\mathcal{N}(\mathcal{X})$ has $n$ vertices it has at most $\binom{n}{d}$ simplices of dimension $d-1$ and ker $\partial_{d-1}$ therefore has dimension at most $\binom{n}{d}$. This dimension can only go down by taking the quotient by im $\partial_d$, so $\beta_{d-1}(\mathcal{N}(\mathcal{X})) \le \binom{n}{d}$. $\quad \blacksquare$

**The number of holes in the union of $\mathcal{F}$.** We now prove Theorem 1 by using Lemma 7.

**Proof of Theorem 1.** Kovalev [13] already established that any union of $n$ convex objects in $\mathbb{R}^3$ has $O(n^3)$ holes. Hence this bound applies to families of translates. It remains to prove that this bound is tight by constructing a family whose union has $\Omega(n^3)$ holes. Let $K$ denote the convex body, and let $\mathcal{F}$ denote the family of $n = 3m$ translates of $K$ constructed above. Let $U = \bigcup_{X \in \mathcal{F}} X$.

Recall that the maximal simplices of $\mathcal{N}(\mathcal{F})$ are identified by Lemma 6. By Lemma 7, the number of holes of $U$ is $\beta_2(\mathcal{N}(\mathcal{F})) + 1$ which equals, by Equation (1), dim ker $\partial_2 - \text{rank} \partial_3 + 1$, where $\partial_i$ denotes the $i$th boundary map of $\mathcal{N}(\mathcal{F})$. We compute $\beta_2(\mathcal{N}(\mathcal{F}))$ by computing explicitly a basis for ker $\partial_2$ and a basis for im $\partial_3$.

To compute a basis of im $\partial_3$, let $\mathcal{S}$ denote the set of 3-simplices of $\mathcal{N}(\mathcal{F})$ containing $B_1$ and let $\mathcal{T}$ stand for the set of images of the simplices of $\mathcal{S}$ under $\partial_3$:

$$ \mathcal{S} = \{\sigma : |\sigma| = 4 \text{ and } B_1 \in \sigma\} \quad \text{and} \quad \mathcal{T} = \{\partial_3 \sigma : \sigma \in \mathcal{S}\}. $$

Observe that $\mathcal{T}$ is a linearly independent family. Indeed, for any $\sigma \in \mathcal{S}$, the 2-simplex $\sigma \setminus \{B_1\}$ has non-zero coefficient in $\partial_3(\sigma)$ but has zero coefficient in $\partial_3(\tau)$ for every $\tau \in \mathcal{S} \setminus \{\sigma\}$. To
see that $\mathcal{T}$ spans $\mathrm{im}\,\partial_3$, let $\sigma$ be a 3-simplex of $\mathcal{N}(\mathcal{T})$. If $B_1 \in \sigma$ then $\sigma \in \mathcal{A}$ and so $\partial_3(\sigma) \in \mathcal{T}$. If $B_1 \notin \sigma$, since $\partial_3 \circ \partial_4 = 0$ we have

$$ \partial_3 \circ \partial_4(\sigma \cup \{B_1\}) = \lambda \partial_3(\sigma) + \sum_{X \in \sigma} \lambda_v \partial_3(\sigma \cup \{B_1\} \setminus \{X\}) = 0 $$

where $\lambda$ and the $\lambda_v$ are in $\{\pm 1\}$. This implies that $\partial_3(\sigma)$ is a sum of $\pm \partial_3(\tau)$ with $\tau \in \mathcal{S}$, and thus lies in the span of $\mathcal{T}$. Therefore, as claimed, $\mathcal{T}$ is a basis of $\mathrm{im}\,\partial_3$.

Now, let $\mathcal{S}'$ denote the set of 2-simplices in $\mathcal{T}$ that contain $B_1$ and let $\mathcal{T}' = \{\partial_2\sigma : \sigma \in \mathcal{S}'\}$. The same arguments yield that $\mathcal{T}'$ is a basis of $\mathrm{im}\,\partial_2$. Also let $\mathcal{S}''$ denote the set of all 2-simplices contained in $\mathcal{T}$.

We can finally compute $\beta_2(\mathcal{N}(\mathcal{T}))$ using the rank-nullity theorem,

$$ \beta_2(\mathcal{N}(\mathcal{T})) = \mathrm{nullity}\,\partial_2 - \mathrm{rank}\,\partial_3 = \dim \mathcal{C}_2(\mathcal{N}(\mathcal{T})) - \mathrm{rank}\,\partial_2 - \mathrm{rank}\,\partial_3 = |\mathcal{S}''| - |\mathcal{T}'| - |\mathcal{T}|. $$

Counting all quadruples in $\Delta_1$ or $\Delta_2$ that contain $B_1$ (taking care that some quadruples appear both in $\Delta_1$ and $\Delta_2$) we have

$$ |\mathcal{T}| = |\mathcal{S}| = 2\binom{2m-1}{3} - \binom{m-1}{3}. $$

Next, counting all triples in $\mathcal{T}$ that contain $B_1$ we have

$$ |\mathcal{T}'| = |\mathcal{S}'| = \binom{3m-1}{2}. $$

Then, counting all triples contained in $\mathcal{N}(\mathcal{T})$, which are the triples in $\Delta_{i,j,k}$ plus $\Delta_{j,k}$ plus the triples in $\Delta_1$ or $\Delta_2$ (accounting for triples belonging to both $\Delta_1$ and $\Delta_2$), we have

$$ |\mathcal{S}''| = m^3 + m(m-1) + 2\binom{2m}{3} - \binom{m}{3}. $$

Finally, using $\binom{a}{b} - \binom{a-1}{b} = \binom{a-1}{b-1}$, we have

$$ \begin{aligned} \beta_2(\mathcal{N}(\mathcal{T})) &= |\mathcal{S}''| - |\mathcal{T}| - |\mathcal{T}'| \\ &= m + m(m-1) + 2\binom{2m}{3} - \binom{m}{3} - 2\binom{2m-1}{3} + \binom{m-1}{3} - \binom{3m-1}{2} \\ &= m^3 + m(m-1) + 2\binom{2m-1}{2} - \binom{m-1}{2} - \binom{3m-1}{2} \\ &= m^3 - m. \end{aligned} $$

So $\mathcal{T}$ is a family of $3m$ translates of a convex body, and the union has $m^3 - m + 1$ holes. $\blacksquare$

References

1. Pankaj K. Agarwal, Sariel Har-Peled, Haim Kaplan, and Micha Sharir. Union of random Minkowski sums and network vulnerability analysis. Discrete Comput. Geom., 52(3):551–582, 2014.

2. Pankaj K. Agarwal, János Pach, and Micha Sharir. State of the union (of geometric objects). In Proc. Joint Summer Research Conf. on Discrete and Computational Geometry: 20 Years Later, volume 452 of Contemp. Math., pages 9–48. AMS, 2008.

3. Boris Aronov, Otfried Cheong, Michael G. Dobbins, and Xavier Goaoc. The number of holes in the union of translates of a convex set in three dimensions. To appear in Discrete Comput. Geom., 2015. URL: http://arxiv.org/abs/1502.01779.

4. Boris Aronov and Micha Sharir. On translational motion planning of a convex polyhedron in 3-space. SIAM J. Comput., 26(6):1785–1803, 1997.

5. Franz Aurenhammer. Voronoi diagrams: A survey of a fundamental geometric data structure. ACM Comput. Surv., 23:345–405, 1991.
10:16 The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

6 Karol Borsuk. On the imbedding of systems of compacta in simplicial complexes. *Fundamenta Mathematicae*, 35:217–234, 1948.

7 Kenneth L. Clarkson and Kasturi Varadarajan. Improved approximation algorithms for geometric set cover. *Discrete Comput. Geom.*, 37(1):43–58, 2007.

8 Alon Efrat and Micha Sharir. On the complexity of the union of fat convex objects in the plane. *Discrete Comput. Geom.*, 23(2):171–189, 2000.

9 Steven Fortune. Voronoi diagrams and Delaunay triangulations. In J. E. Goodman and J. O'Rourke, editors, *Handbook of Discrete and Computational Geometry*, chapter 23, pages 513–528. CRC Press LLC, Boca Raton, FL, 2 edition, 2004.

10 Allen Hatcher. *Algebraic topology*. Cambridge University Press, Cambridge, UK, 2002.

11 Christian Icking, Rolf Klein, Ngoc-Minh Lé, and Lihong Ma. Convex distance functions in 3-space are different. *Fund. Inform.*, 22:331–352, 1995. doi:10.3233/FI-1995-2242.

12 Klara Kedem, Ron Livne, János Pach, and Micha Sharir. On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. *Discrete Comput. Geom.*, 1(1):59–71, 1986.

13 Mikhail D. Kovalev. Svoistvo vypuklykh mnozhestv i ego prilozhenie (A property of convex sets and its application). *Mat. Zametki*, 44:89–99, 1988. In Russian.

14 Joseph S. B. Mitchell and Joseph O'Rourke. Computational geometry column 42. *Int. J. Comput. Geom. Ap.*, 11(05):573–582, 2001.

15 James R. Munkres. *Elements of Algebraic Topology*. Addison-Wesley, Menlo Park, CA, 1984.

16 János Pach and Gábor Tardos. On the boundary complexity of the union of fat triangles. *SIAM J. Comput.*, 31(6):1745–1760, 2002.

17 Micha Sharir. Algorithmic motion planning. In J. E. Goodman and J. O'Rourke, editors, *Handbook of Discrete and Computational Geometry*, chapter 47, pages 1037–1064. CRC Press LLC, Boca Raton, FL, 2 edition, 2004.

18 Micha Sharir and Pankaj K. Agarwal. *Davenport-Schinzel Sequences and Their Geometric Applications*. Cambridge University Press, New York, NY, USA, 2010.

19 Boaz Tagansky. *The Complexity of Substructures in Arrangements of Surfaces*. PhD thesis, Tel Aviv University, 1996.