# On a problem of Danzer

Nabil Mustafa, Saurabh Ray

► To cite this version:

Nabil Mustafa, Saurabh Ray. On a problem of Danzer. 26th Annual European Symposium on Algorithms (ESA 2018), Aug 2018, Helsinki, Finland. pp.64:1-64:8, 10.4230/LIPIcs.ESA.2018.64. hal-01890699

HAL Id: hal-01890699

https://hal.science/hal-01890699

Submitted on 31 May 2020

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
# On a Problem of Danzer

Nabil H. Mustafa<fnref n="1" />

Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, Equipe A3SI, ESIEE Paris
mustafan@esiee.fr

Saurabh Ray

Department of Computer Science, NYU Abu Dhabi, United Arab Emirates
saurabh.ray@nyu.edu

**Abstract**

Let $\mathcal{C}$ be a bounded convex object in $\mathbb{R}^d$, and $\mathcal{P}$ a set of $n$ points lying outside $\mathcal{C}$. Further let $c_p, c_q$ be two integers with $1 \le c_q \le c_p \le n - \lfloor \frac{d}{2} \rfloor$, such that every $c_p + \lfloor \frac{d}{2} \rfloor$ points of $\mathcal{P}$ contains a subset of size $c_q + \lfloor \frac{d}{2} \rfloor$ whose convex-hull is disjoint from $\mathcal{C}$. Then our main theorem states the existence of a partition of $\mathcal{P}$ into a small number of subsets, each of whose convex-hull is disjoint from $\mathcal{C}$. Our proof is constructive and implies that such a partition can be computed in polynomial time.

In particular, our general theorem implies polynomial bounds for Hadwiger-Debrunner $(p, q)$ numbers for balls in $\mathbb{R}^d$. For example, it follows from our theorem that when $p > q \ge (1 + \beta) \cdot \frac{d}{2}$ for $\beta > 0$, then any set of balls satisfying the HD$(p, q)$ property can be hit by $O\left(q^2 p^{1+\frac{1}{\beta}} \log p\right)$ points. This is the first improvement over a nearly 60-year old exponential bound of roughly $O(2^d)$.

Our results also complement the results obtained in a recent work of Keller *et al*. where, apart from improvements to the bound on HD$(p, q)$ for convex sets in $\mathbb{R}^d$ for various ranges of $p$ and $q$, a polynomial bound is obtained for regions with low union complexity in the plane.

**2012 ACM Subject Classification** Theory of computation → Computational geometry

**Keywords and phrases** Convex polytopes, Hadwiger-Debrunner numbers, Epsilon-nets, Balls

**Digital Object Identifier** 10.4230/LIPIcs.ESA.2018.64

## 1 Introduction

Given a finite set $\mathcal{C}$ of geometric objects in $\mathbb{R}^d$, we say that $\mathcal{C}$ satisfies the HD$(p, q)$ property if for any set $C' \subseteq \mathcal{C}$ of size $p$, there exists a point in $\mathbb{R}^d$ common to at least $q$ objects of $\mathcal{C}'$. The goal then is to show that there exists a small set $Q$ of points in $\mathbb{R}^d$ such that each object of $\mathcal{C}$ contains some point of $Q$; such a $Q$ is called a hitting set for $\mathcal{C}$.

These bounds for a set $\mathcal{C}$ of convex sets in $\mathbb{R}^d$ have been studied since the 1950s (see the surveys [7, 8, 15]), and it was only in 1991 that Alon and Kleitman [1], in a breakthrough result, gave an upper-bound that is *independent of* $|\mathcal{C}|$. Unfortunately it depends exponentially on $p, q$ and $d$. For the case where $\mathcal{C}$ consists of arbitrary convex objects, the current best bounds remain exponential in $p, q$ and $d$.

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

<footnote n="1">¹ The work of Nabil H. Mustafa in this paper has been supported by the grant ANR SAGA (JCJC-14-CE25-0016-01).</footnote>
**▶ Theorem A ([1, 9]).** Let $\mathcal{C}$ be a finite set of convex objects in $\mathbb{R}^d$ satisfying the HD$(p, q)$ property, where $p, q$ are two integers with $p \ge q \ge d+1$. Then there exists a hitting set for $\mathcal{C}$ of size

$$ egin{cases} O\left(p^{\frac{d}{q}-1} \cdot \log^{c' d^3 \log d} p\right), \\ (p-q) + O\left(\left(\frac{p}{q}\right)^d \log^{c' d^3 \log d} \left(\frac{p}{q}\right)\right), & \text{for } q \ge \log p \\ p-q+2, & \text{for } q \ge p^{1-\frac{1}{d}+\epsilon}, p \ge p(d, \epsilon). \end{cases} $$

where $c'$ is an absolute constant independent of $|\mathcal{C}|, p, q$ and $d$, and $p(d, \epsilon)$ is a function depending only on $d$ and $\epsilon$.

Consider the basic case where $\mathcal{C}$ is a set of balls in $\mathbb{R}^d$ satisfying the HD$(p, q)$ property. Theorem A implies – ignoring logarithmic factors and for general values of $p$ and $q$ – the existence of a hitting set of size no better than $O(p^d)$. Furthermore, it requires $q \ge d+1$ – a necessary condition for arbitrary convex objects<fnref n="2" /> but not for balls.

Almost 60 years ago, Danzer [4, 5] considered the HD$(p, q)$ problem for balls. The best bound that we are aware of, derived from the survey of Eckhoff [7] by combining inequalities (4.2), (4.4) and (4.5), is stated below. It is better than the one from Theorem A quantitatively, but also in that it gives a bound requiring only that $q \ge 2$. Further, for a very specific case – namely when $p = q$ and $(d-q)$ is $O(\log d)$ – it succeeds in giving polynomial bounds.

**▶ Theorem B ([7]).** Let $\mathcal{B}$ be a finite set of balls in $\mathbb{R}^d$. If $\mathcal{B}$ satisfies the HD$(p, q)$ property for some $d \ge p \ge q \ge 2$, then there exists a hitting set for $\mathcal{B}$ of size at most

$$ \sqrt{\frac{3\pi}{2}} \cdot 2^{d-q} \cdot \left( (p-q) \cdot 2^q \cdot d^{\frac{3}{2}} \cdot g(d) + 4(d-q+2)^{\frac{3}{2}} \cdot g(d-q+2) \right) $$

where $g(x) = \log x + \log \log x + 1$. Ignoring logarithmic terms, the above bound is of the form $\Theta((p-q) \cdot 2^d \cdot d^{\frac{3}{2}} + 2^{d-q} \cdot (d-q)^{\frac{3}{2}})$. If $p \ne q$ the first term dominates, otherwise the second term dominates.

Turning towards the lower-bound for the case where $\mathcal{C}$ is a set of unit balls in $\mathbb{R}^d$, Bourgain and Lindenstrauss [2] proved a lower-bound of $1.0645^d$ when $p = q = 2$ in $\mathbb{R}^d$, i.e., one needs at least $1.0645^d$ points to hit all pairwise intersecting unit balls in $\mathbb{R}^d$.

## Our Result

We consider a more general set up for the HD$(p, q)$ problem, as follows.

Let $\mathcal{C}$ be a convex object in $\mathbb{R}^d$, and $P$ a set of $n$ points lying outside $\mathcal{C}$. For each $p \in P$, let $H_p$ be the set of hyperplanes separating $p$ from $\mathcal{C}$. Let $C_p$ be the set of points in $\mathbb{R}^d$ dual to the hyperplanes in $H_p$ (see [12, Chapter 5.1]), and let $S = \{C_p: p \in P\}$.

Our goal is to study the HD$(p, q)$ property for $S$ – namely, that out of every $p$ objects of $S$, there exists a point in $\mathbb{R}^d$ common to at least $q$ of them. This is equivalent to the property of $\mathcal{C}$ and $P$ that out of every $p$-sized set $P' \subseteq P$, there exists a hyperplane separating $\mathcal{C}$ from a $q$-sized subset $P'' \subset P'$ – or equivalently, $\mathrm{conv}(P'')$ is disjoint from $\mathcal{C}$.

Our main theorem is the following. For a simpler expression, let $c_q, c_p$ be two positive integers such that $p = c_p + \lfloor \frac{d}{2} \rfloor$ and $q = c_q + \lfloor \frac{d}{2} \rfloor$.

<footnote n="2">² There are easy examples, e.g. when the convex objects are hyperplanes in $\mathbb{R}^d$.</footnote>
**Theorem 1.** Let C be a bounded convex object in $\mathbb{R}^d$ and P a set of n points lying outside C. Further let $c_p, c_q$ be two integers, with $1 \le c_q \le c_p \le n - \lfloor \frac{d}{2} \rfloor$, such that for every $c_p + \lfloor \frac{d}{2} \rfloor$ points of P, there exists a subset of size $c_q + \lfloor \frac{d}{2} \rfloor$ whose convex-hull is disjoint from C. Then the points of P can be partitioned into

$$ \lambda_d(c_p, c_q) = K_2 \frac{d}{c_q} \cdot (\sqrt{2}K_1)^{\frac{d}{c_q}} \cdot (\lfloor d/2 \rfloor + c_q)^2 \cdot (\lfloor d/2 \rfloor + c_p)^{1+\frac{\lfloor d/2 \rfloor-1}{c_q}} \cdot \log(\lfloor d/2 \rfloor + c_p) $$

sets, each of whose convex-hull is disjoint from C. Here $K_1, K_2$ are absolute constants independent of n, d, $c_p$ and $c_q$. Furthermore, such a partition can be computed in polynomial time.

The proof, presented in Section 2, is a combination of three ingredients: the Alon-Kleitman technique [1], bounds on independent sets in hypergraphs [9] and bounds on ($\le k$)-sets for half-spaces [3]. It is an extension of the proof in [14] which studied Carathéodory's theorem in this setting.

**Remark.** The restriction that $q \ge \lfloor \frac{d}{2} \rfloor + 1$ is necessary – as can be seen when P form the vertices of a cyclic polytope in $\mathbb{R}^d$ and C is a slightly shrunk copy of $\text{conv}(P)$.

**Remark.** Note that when $c_q \ge \beta \cdot \frac{d}{2}$ for any absolute constant $\beta > 0$, the above bound is polynomial in the dimension $d$ – it is upper-bounded by $O(q^2 p^{1+\frac{1}{\beta}} \log p)$.

**Remark.** It was shown in [13] that $C_p$ is a convex object in $\mathbb{R}^d$ and thus the bounds of Theorem A apply. As before, Theorem 1 substantially improves upon this, as the bounds following from Theorem A are exponential in $d$ and furthermore, require $q \ge d + 1$.

As an immediate corollary of Theorem 1, we obtain the first improvements to the old bound on the $(p, q)$ problem for balls in $\mathbb{R}^d$. The bound in Theorem B is exponential in $d$ – except in special cases where $p = q$ and $(d - q)$ is $^3 O(\log d)$. On the other hand, our result gives polynomial bounds as long as $q \ge \beta d$ for any constant $\beta > \frac{1}{2}$.

**Corollary 2 (Hadwiger-Debrunner $(p, q)$ bound for balls in $\mathbb{R}^d$).** Let $\mathcal{B}$ be collection of balls in $\mathbb{R}^d$ such that for every subset of $c_p + \lfloor \frac{d+1}{2} \rfloor$ balls in $\mathcal{B}$, some $c_q + \lfloor \frac{d+1}{2} \rfloor$ have a common intersection, where $c_p$ and $c_q$ are integers such that $1 \le c_q \le c_p \le n - \lfloor \frac{d+1}{2} \rfloor$. Then there exists a set $X$ of $\lambda_{d+1}(c_p, c_q)$ points that form a hitting set for the balls in $\mathcal{B}$. Here $\lambda_{d+1}(\cdot, \cdot)$ is the function defined in the statement of Theorem 1.

**Proof.** Observe that one can stereographically ‘lift’ balls in $\mathbb{R}^d$ to caps of a sphere $S$ in $\mathbb{R}^{d+1}$, where a cap of a sphere is a portion of the sphere contained in a half-space that doesn’t contain the center of the sphere. Thus we will prove a slightly more general result where $\mathcal{B}$ consists of caps of a $d$-dimensional sphere $S$ embedded in $\mathbb{R}^{d+1}$.

For a point $x \in S$, let $h_x$ denote the hyperplane tangent to $S$ at $x$. For any point $y$ lying outside $S$, define the separating set of $y$ to be

$$ S_y = \{z \in S : h_z \text{ separates } y \text{ and } S\}. $$

Geometrically, $S_y$ is the set of points of $S$ ‘visible’ from $y$, and form a cap of $S$. Furthermore, for any cap $K$ of $S$, there is a unique point $w$ such that $K = S_w$. We denote this point $w$ by $\text{apex}(K)$.

<footnote n="3">³ Recall that Theorem B assumes $q \le p \le d$.</footnote>
64:4 On a Problem of Danzer

Given the set of caps $\mathcal{B}$ on $S$, consider the point set

$$ \operatorname{apex}(\mathcal{B}) = \{\operatorname{apex}(B) : B \in \mathcal{B}\}. $$

Observe that for a point $x \in S$ and a cap $B \in \mathcal{B}$, $x \in B$ if and only if $x \in S_{\operatorname{apex}(B)}$. As $\mathcal{B}$ satisfies the $(p, q)$ property – namely that for every $p$-sized subset $\mathcal{B}'$ of $\mathcal{B}$, there exists a point $x \in S$ lying in some $q$ elements of $\mathcal{B}'$ – we have that for every $p$-sized subset $A'$ of $\operatorname{apex}(\mathcal{B})$, there exists a point $x \in S$ lying in the separating set of some $q$ points of $A'$. In other words, $h_x$ separates these $q$ points from $S$.

Applying Theorem 1 with $C = S$ and $P = \operatorname{apex}(\mathcal{B})$ in dimension $d+1$, we conclude that $P$ can be partitioned into a family $\Xi$ of $\lambda_{d+1}(c_p, c_q)$ sets, each of whose convex hull is disjoint from $S$. Consider a set $P' \in \Xi$. Since the convex hull of $P'$ is disjoint from $S$, we can find a hyperplane $h_x$ tangent to $S$ at $x$ such that $h_x$ separates $P'$ from $S$. This implies that all the caps in $\mathcal{B}$ corresponding to the points in $P'$ contain the point $x$. Thus for each set of $\Xi$ we obtain a point which is contained in all the caps corresponding to the points in that set. These $|X| = \lambda_{d+1}(c_p, c_q)$ points form the required set $X$. $\quad$

Our results complement the recent results of Keller, Smorodinsky and Tardos [9, 10] who obtain polynomial bounds for regions of low union complexity in the plane.

## 2 Proof of Theorem 1

Given a set $P$ of points in $\mathbb{R}^d$ and an integer $k \ge 1$, a set $P' \subseteq P$ is called a $k$-set of $P$ if $|P'| = k$ and if there exists a half-space $h$ in $\mathbb{R}^d$ such that $P' = P \cap h$. A set $P' \subseteq P$ is called a $(\le k)$-set if $P'$ is a $l$-set for some $l \le k$. The next well-known theorem gives an upper-bound on the number of $(\le k)$-sets in a point set (see [17]).

**Theorem 3 (Clarkson-Shor [3]).** For any integer $k \ge \lfloor \frac{d}{2} \rfloor + 1$, the number of $(\le k)$-sets of any set of $n$ points in $\mathbb{R}^d$ is at most

$$ \kappa_d(n, k) = 2 \left( \frac{K_1}{|d/2|} \right)^{\lfloor d/2 \rfloor} \binom{n}{\lfloor d/2 \rfloor} (k + \lfloor d/2 \rfloor)^{\lfloor d/2 \rfloor} \le \kappa'_d(k) \cdot n^{\lfloor d/2 \rfloor}, \quad (1) $$

where $\kappa'_d(k) = 2K_1^d|d/2|^{-\lfloor d/2 \rfloor} \left(1 + \frac{k}{|d/2|}\right)^{\lfloor d/2 \rfloor}$ and $K_1 \ge e$ is an absolute constant independent of $n$, $d$ and $k$.

**Definition 4 (Depth).** Given a set $P$ of $n$ points in $\mathbb{R}^d$ and any set $Q \subseteq P$, define the depth of $Q$ with respect to $P$, denoted depth$_P(Q)$, to be the minimum number of points of $P$ contained in any half-space containing $Q$.

For two parameters $l \ge k \ge 2$, let $\tau_d(n, k, l)$ denote the maximum number of subsets of size $k$ and depth at most $l$ with respect to $P$ in any set $P$ of $n$ points in $\mathbb{R}^d$:

$$ \tau_d(n, k, l) = \max_{\substack{P \subseteq \mathbb{R}^d \\ |P| = n}} |\{Q \subseteq P : |Q| = k \text{ and depth}_P(Q) \le l\}|. $$

The following statement is easily implied by an application of the Clarkson-Shor technique [3] (e.g., see [16]).

**Theorem 5.** For parameters $l \ge k \ge \lfloor \frac{d}{2} \rfloor + 1$,

$$ \tau_d(n, k, l) \le e \cdot \kappa_d(n, k) \cdot l^{k-\lfloor d/2 \rfloor}, $$

where the function $\kappa(\cdot, \cdot)$ is as defined in Equation (1).
**Proof.** Let $P$ be any set of $n$ points in $\mathbb{R}^d$. Let $t$ be the number of sets of $P$ of size $k$ and depth at most $l$. Pick each element of $P$ independently with probability $\rho = \frac{1}{l}$ to get a random sample $R$. The expected number of $k$-sets in $R$ satisfies

$$ \begin{aligned} \rho^k \cdot (1 - \rho)^{l-k} \cdot t &\le \mathbb{E}[\text{number of } k\text{-sets in } R] \\ &\le 2 \left( \frac{K_1}{\lfloor d/2 \rfloor} \right)^{\lfloor \frac{d}{2} \rfloor} \mathbb{E} \left[ \left( \left( \lfloor R \rfloor / \lfloor \frac{d}{2} \rfloor \right) \right) \left( k + \lfloor \frac{d}{2} \rfloor \right)^{\lfloor \frac{d}{2} \rfloor} \right] \\ &= 2 \left( \frac{K_1}{\lfloor d/2 \rfloor} \right)^{\lfloor \frac{d}{2} \rfloor} \left( \left( \lfloor \frac{d}{2} \rfloor \right) \rho^{\lfloor \frac{d}{2} \rfloor} \right) \left( k + \lfloor \frac{d}{2} \rfloor \right)^{\lfloor \frac{d}{2} \rfloor} \\ &= \kappa_d(n, k) \cdot \rho^{\lfloor \frac{d}{2} \rfloor} \\ \implies t &\le \frac{\kappa_d(n, k) \cdot \rho^{\lfloor \frac{d}{2} \rfloor}}{\rho^k \cdot (1 - \rho)^{l-k}} \le e \cdot \kappa_d(n, k) \cdot l^{k-\lfloor d/2 \rfloor}, \end{aligned} $$

as $(1 - \frac{1}{l})^{-(l-k)} \le e$ for any $l \ge k \ge 2$.

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

**► Lemma 6.** Let $C$ be a bounded convex object in $\mathbb{R}^d$, and $P$ a set of $n$ points lying outside $C$. Let $p \ge q \ge \lfloor \frac{d}{2} \rfloor + 1$ be parameters such that for every subset $Q \subseteq P$ of size $p$, there exists a set $Q' \subset Q$ of size $q$ such that $Q'$ can be separated from $C$ by a hyperplane. Then there exists a hyperplane separating at least

$$ (2q p^{q-1} \cdot e \kappa'_{d}(q))^{\frac{1}{\lfloor d/2 \rfloor - q}} $$

fraction of the points of $P$ from $C$.

**Proof.** From [6, 9], it follows that the number of distinct $q$-tuples of $P$ that can be separated from $C$ by a hyperplane is, assuming that $n \ge 2p$, at least

$$ \frac{n-p+1}{n-q+1} \binom{n}{q} \ge \frac{n^q}{2q p^{q-1}}. $$

Let $l$ be the maximum depth (Definition 4) of any of these separable $q$-tuples. The number of such tuples is therefore at most $\tau_d(n, q, l)$. Thus by Theorem 5 we must have

$$ \frac{n^q}{2q p^{q-1}} \le \tau_d(n, q, l) \le e \kappa_d(n, q) l^{q-\lfloor d/2 \rfloor}. $$

Re-arranging the terms and from inequality (1), we get

$$ \begin{aligned} l &\ge \left( \frac{n^q}{2q p^{q-1} \cdot e \kappa_d(n, q)} \right)^{\frac{1}{q-\lfloor d/2 \rfloor}} \\ &\ge \left( \frac{n^q}{2q p^{q-1} \cdot e \kappa'_d(q) n^{\lfloor \frac{d}{2} \rfloor}} \right)^{\frac{1}{q-\lfloor d/2 \rfloor}} \\ &= n \cdot (2q p^{q-1} \cdot e \kappa'_d(q))^{\frac{1}{\lfloor d/2 \rfloor - q}}. \end{aligned} $$

Thus one of the separable $q$-tuples, say $P' \subseteq P$, must have depth at least $l$; in other words, the hyperplane separating $P'$ from $C$ must contain at least $l$ points of $P$. This is the required hyperplane.

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

We now prove a weighted version of the above statement.
**Corollary 7.** Let $C$ be a bounded convex object in $\mathbb{R}^d$, and $P$ a weighted set of $n$ points lying outside $C$, where the weight of each point $p \in P$ is a non-negative rational number. Let $p \ge q \ge \lfloor \frac{d}{2} \rfloor + 1$ be parameters such that for every subset $Q \subseteq P$ of size $p$, there exists a set $Q' \subset Q$ of size $q$ such that $Q'$ can be separated from $C$ by a hyperplane. Then there exists a hyperplane separating a set of points whose weight is at least

$$ \alpha_d(p, q) = (2e \kappa_d'(q) q^q p^{q-1})^{\frac{1}{\lfloor d/2 \rfloor - q}} $$

fraction of the total weight of the points in $P$.

**Proof.** By appropriately scaling all the rational weights, we may assume that each weight is a non-negative integer and we replace a point with weight $m$ by $m$ unweighted copies of the point. Let $P'$ be the new set of points. Observe that any set $S$ of $pq$ points in $P'$ either contains $q$ copies of some point in $P$ or it contains $p$ distinct points from $P$. In either case, there is hyperplane separating $q$ points of $S$ from $C$. Thus, we can apply Lemma 6 to the point set $P'$ with the parameter $p$ in the lemma replaced by $pq$. The result follows. ◀

Finally we return to the proof of the main theorem.

**Theorem 1.** Let $C$ be a bounded convex object in $\mathbb{R}^d$ and $P$ a set of $n$ points lying outside $C$. Further let $c_p, c_q$ be two integers, with $1 \le c_q \le c_p \le n - \lfloor \frac{d}{2} \rfloor$, such that for every $c_p + \lfloor \frac{d}{2} \rfloor$ points of $P$, there exists a subset of size $c_q + \lfloor \frac{d}{2} \rfloor$ whose convex-hull is disjoint from $C$. Then the points of $P$ can be partitioned into

$$ \lambda_d(c_p, c_q) = K_2 \frac{d}{c_q} \cdot (\sqrt{2}K_1)^{\frac{d}{c_q}} \cdot (\lfloor d/2 \rfloor + c_q)^2 \cdot (\lfloor d/2 \rfloor + c_p)^{1+\frac{|d/2|-1}{c_q}} \cdot \log(\lfloor d/2 \rfloor + c_p) $$

sets, each of whose convex-hull is disjoint from $C$. Here $K_1, K_2$ are absolute constants independent of $n, d, c_p$ and $c_q$. Furthermore, such a partition can be computed in polynomial time.

**Proof.** Let $p = c_p + \lfloor d/2 \rfloor$ and $q = c_q + \lfloor d/2 \rfloor$. Let $\mathcal{H}$ be the set of all hyperplanes separating a distinct subset of points of $P$ from $C$. As the number of subsets of $P$ is finite, one can assume that $\mathcal{H}$ is also finite. Consider the following linear program on $|\mathcal{H}|$ variables $\{u_h \ge 0: h \in \mathcal{H}\}$:

$$ \min \sum_{h \in \mathcal{H}} u_h, \quad \text{such that} \quad \forall r \in P: \sum_{h \in \mathcal{H}} u_h \ge 1. \qquad (2) $$
$h$ separates $r$ from $C$

The LP-dual to the above program, on $|P|$ variables $\{w_r \ge 0: r \in P\}$, is:

$$ \max \sum_{p \in P} w_p, \quad \text{such that} \quad \forall h \in \mathcal{H}: \sum_{r \in P} w_r \le 1. \qquad (3) $$
$h$ separates $r$ from $C$

Consider an optimal solution $w^*$ of the dual linear program and interpret $w_r^*$ as the weight of each $r \in P$. Since the weights are rational, by Corollary 7, there exists a hyperplane $h \in \mathcal{H}$ separating a subset of $P$ of combined weight at least $\epsilon = \alpha_d(p, q)$ fraction of the total weight of all the points. Since the total weight of the points in any half-space is constrained to be at most 1 by the linear program, the total weight of all the points of $P$ must be at most $\frac{1}{\epsilon}$. In other words, the optimal value of linear program (3) is at most $\frac{1}{\epsilon}$. Since the optimal values of both linear programs are equal due to strong duality, the optimal value of linear program (2) is also at most $\frac{1}{\epsilon}$.
Let $u^*$ be the optimal solution of linear program (2). If we interpret $u_h$ as the weight of the hyperplane $h$, the constraints of the program imply that each point is separated by a set of hyperplanes in $\mathcal{H}$ whose combined weight is at least 1 out of a total weight of at most $\frac{1}{\epsilon}$ – in other words, at least $\epsilon$-th fraction of the total weight of $\mathcal{H}$. By associating with each hyperplane the half-space bounded by it and not containing $C$, and using the $\epsilon$-net theorem for half-spaces in $\mathbb{R}^d$ (see [11]), there exists a set of $O(\frac{d}{\epsilon} \log \frac{1}{\epsilon})$ hyperplanes which together separate all points of $P$ from $C$. Recalling that

$$ \frac{1}{\epsilon} = \frac{1}{\alpha_d(p, q)} = (2e \kappa'_d(q) q^q p^{q-1})^{\frac{1}{q-\lfloor d/2 \rfloor}} = (2e \kappa'_d(q) q^q p^{q-1})^{\frac{1}{c_q}}. $$

and that $\kappa'_d(q) = 2K_1^d \lfloor d/2 \rfloor^{-\lfloor d/2 \rfloor} \left(1 + \frac{q}{\lfloor d/2 \rfloor}\right)^{\lfloor d/2 \rfloor}$, we get

$$ \frac{1}{\epsilon} = \left( 4K_1^d e^{\lfloor d/2 \rfloor - \lfloor d/2 \rfloor} \left(1 + \frac{q}{\lfloor d/2 \rfloor}\right)^{\lfloor d/2 \rfloor} q^q p^{q-1} \right)^{\frac{1}{c_q}} \\ \le (4K_1^{d+1} \lfloor d/2 \rfloor^{-d} (c_q+d)^{\lfloor d/2 \rfloor} q^q p^{q-1})^{\frac{1}{c_q}} \quad (\text{using } e \le K_1 \text{ and } q = c_q + \lfloor d/2 \rfloor) $$

$$ \le (4K_1^{d+1} \lfloor d/2 \rfloor^{-d} (c_q+d)^{\lfloor d/2 \rfloor} q^{c_q+\lfloor d/2 \rfloor} p^{c_q+\lfloor d/2 \rfloor-1})^{\frac{1}{c_q}} $$

$$ = O \left( K_1^{\frac{d}{c_q}} \lfloor d/2 \rfloor^{-\frac{d}{c_q}} (c_q + d)^{\frac{\lfloor d/2 \rfloor}{c_q}} (c_q + \lfloor d/2 \rfloor)^{1+\frac{\lfloor d/2 \rfloor}{c_q}} (c_p + \lfloor d/2 \rfloor)^{1+\frac{\lfloor d/2 \rfloor-1}{c_q}} \right) $$

$$ = O \left( K_1^{\frac{d}{c_q}} d^{2+\frac{\lfloor d/2 \rfloor-1}{c_q}} \left(1 + \frac{c_q}{d}\right)^{\frac{\lfloor d/2 \rfloor}{c_q}} \left(1 + \frac{c_q}{\lfloor d/2 \rfloor}\right)^{1+\frac{\lfloor d/2 \rfloor}{c_q}} \left(1 + \frac{c_p}{\lfloor d/2 \rfloor}\right)^{1+\frac{\lfloor d/2 \rfloor-1}{c_q}} \right) $$

$$ = O \left( K_1^{\frac{d}{c_q}} d^{2+\frac{\lfloor d/2 \rfloor-1}{c_q}} e^{\frac{c_q}{d} \cdot \frac{\lfloor d/2 \rfloor}{c_q}} \left(1 + \frac{c_q}{\lfloor d/2 \rfloor}\right) e^{\frac{c_q}{\lfloor d/2 \rfloor} \cdot \frac{\lfloor d/2 \rfloor}{c_q}} \left(1 + \frac{c_p}{\lfloor d/2 \rfloor}\right)^{1+\frac{\lfloor d/2 \rfloor-1}{c_q}} \right) $$

$$ = O \left( K_1^{\frac{d}{c_q}} d^{2+\frac{\lfloor d/2 \rfloor-1}{c_q}} \left(1 + \frac{c_q}{\lfloor d/2 \rfloor}\right) \left(1 + \frac{c_p}{\lfloor d/2 \rfloor}\right)^{1+\frac{\lfloor d/2 \rfloor-1}{c_q}} \right) $$

$$ = O \left( K_1^{\frac{d}{c_q}} 2^{\frac{d}{2c_q}} (\lfloor d/2 \rfloor + c_q) (\lfloor d/2 \rfloor + c_p)^{1+\frac{\lfloor d/2 \rfloor-1}{c_q}} \right) $$

$$ = O \left( (\sqrt{2}K_1)^{\frac{d}{c_q}} (\lfloor d/2 \rfloor + c_q) (\lfloor d/2 \rfloor + c_p)^{1+\frac{\lfloor d/2 \rfloor-1}{c_q}} \right). $$

The Big-Oh notation here does not hide dependencies on $d$ – namely we do not treat $d$ as a constant. From the above it follows that

$$ \log \frac{1}{\epsilon} = O \left( c_q^{-1} \left( \lfloor d/2 \rfloor + c_q \right) \log \left( \lfloor d/2 \rfloor + c_p \right) \right). $$

Thus, $\frac{d}{\epsilon} \log \frac{1}{\epsilon}$ is

$$ O \left( d \cdot \left( (\sqrt{2}K_1)^{\frac{d}{c_q}} (\lfloor d/2 \rfloor + c_q) (\lfloor d/2 \rfloor + c_p)^{1+\frac{\lfloor d/2 \rfloor-1}{c_q}} \right) \cdot (c_q^{-1} (\lfloor d/2 \rfloor + c_q) \log (\lfloor d/2 \rfloor + c_p)) \right) $$

which simplifies to

$$ O \left( \frac{d}{c_q} (\sqrt{2}K_1)^{\frac{d}{c_q}} (\lfloor d/2 \rfloor + c_q)^2 (\lfloor d/2 \rfloor + c_p)^{1+\frac{\lfloor d/2 \rfloor-1}{c_q}} \log(\lfloor d/2 \rfloor + c_p) \right). $$

Since linear programs can be solved in polynomial time and epsilon nets can be computed in polynomial time, the partition of $P$ into the above number of sets can be achieved in polynomial time. The theorem follows. ▼

<figure><img src="image_5.png" /></figure>
References

1 N. Alon and D. Kleitman. Piercing convex sets and the Hadwiger–Debrunner (p, q)-problem. *Adv. Math.*, 96(1):103–112, 1992.

2 J. Bourgain and J. Lindenstrauss. On covering a set in $R^n$ by balls of the same diameter. In *Geometric Aspects of Functional Analysis*, pages 138–144. Springer Berlin Heidelberg, 1991.

3 K. Clarkson and P. Shor. Applications of random sampling in computational geometry, II. *Discrete & Computational Geometry*, 4(5):387–421, 1989.

4 L. Danzer. *Über zwei Lagerungsprobleme; Abwandlungen einer Vermutung von T. Gallai*. PhD thesis, Techn. Hochschule Munchen, 1960.

5 L. Danzer. Über durchschnittseigenschaften n-dimensionaler kugelfamilien. *J. Reine Angew. Math.*, 208:181–203, 1961.

6 D. de Caen. Extension of a theorem of Moon and Moser on complete subgraphs. *Ars Combin.*, 16:5–10, 1983.

7 J. Eckhoff. A survey of the Hadwiger-Debrunner (p, q)-problem. In *Discrete and Computational Geometry: The Goodman-Pollack Festschrift*, pages 347–377. Springer, 2003.

8 A. Holmsen and R. Wenger. Helly-type theorems and geometric transversals. In J. E. Goodman, J. O'Rourke, and C. D. Tóth, editors, *Handbook of Discrete and Computational Geometry*, pages 91–123. CRC Press LLC, 2017.

9 C. Keller, S. Smorodinsky, and G. Tardos. Improved bounds on the Hadwiger-Debrunner numbers. *Israel J. of Math., to appear*, 2017.

10 C. Keller, S. Smorodinsky, and G. Tardos. On max-clique for intersection graphs of sets and the hadwiger-debrunner numbers. In *Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 2254–2263, 2017.

11 A. Kupavskii, N. H. Mustafa, and J. Pach. Near-optimal lower bounds for $\epsilon$-nets for half-spaces and low complexity set systems. In Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, editors, *A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek*, pages 527–541. Springer International Publishing, 2017.

12 J. Matoušek. *Lectures in Discrete Geometry*. Springer-Verlag, New York, NY, 2002.

13 N. H. Mustafa and S. Ray. Weak $\epsilon$-nets have a basis of size $O(1/\epsilon \log 1/\epsilon)$. *Comp. Geom: Theory and Appl.*, 40(1):84–91, 2008.

14 N. H. Mustafa and S. Ray. An optimal generalization of the colorful Carathéodory theorem. *Discrete Mathematics*, 339(4):1300–1305, 2016.

15 N. H. Mustafa and K. Varadarajan. Epsilon-approximations and epsilon-nets. In J. E. Goodman, J. O'Rourke, and C. D. Tóth, editors, *Handbook of Discrete and Computational Geometry*, pages 1241–1268. CRC Press LLC, 2017.

16 S. Smorodinsky, M. Sulovský, and U. Wagner. On center regions and balls containing many points. In *Proceedings of the 14th annual International Conference on Computing and Combinatorics*, COCOON '08, pages 363–373, 2008.

17 U. Wagner. $k$-sets and $k$-facets. In J.E. Goodman, J. Pach, and R. Pollack, editors, *Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemporary Mathematics*, pages 231–255. American Mathematical Society, 2008.