Algoresearch L.L.C., Milwaukee, WI, USA<EMAIL_ADDRESS>0000-0002-1118-0321 Department of Mathematics, California State University
Northridge, Los Angeles, CA; and Department of Computer Science, Tufts
University, Medford, MA, USA<EMAIL_ADDRESS>0000-0002-8769-3190 Adrian
Dumitrescu and Csaba D. Tóth [500]Mathematics of computing Approximation
algorithms [500]Theory of computation Computational geometry

# Finding Points in Convex Position in Density-Restricted Sets

Adrian Dumitrescu  Csaba D. Tóth

###### Abstract

For a finite set $A\subset\mathbb{R}^{d}$, let $\Delta(A)$ denote the spread
of $A$, which is the ratio of the maximum pairwise distance to the minimum
pairwise distance. For a positive integer $n$, let $\gamma_{d}(n)$ denote the
largest integer such that any set $A$ of $n$ points in general position in
$\mathbb{R}^{d}$, satisfying $\Delta(A)\leq\alpha n^{1/d}$ for a fixed
$\alpha>0$, contains at least $\gamma_{d}(n)$ points in convex position. About
$30$ years ago, Valtr proved that $\gamma_{2}(n)=\Theta(n^{1/3})$. Since then
no further results have been obtained in higher dimensions. Here we continue
this line of research in three dimensions and prove that
$\gamma_{3}(n)=\Theta(n^{1/2})$. The lower bound implies the following
approximation: Given any $n$-element point set $A\subset\mathbb{R}^{3}$ in
general position, satisfying $\Delta(A)\leq\alpha n^{1/3}$ for a fixed
$\alpha$, a $\Omega(n^{-1/6})$-factor approximation of the maximum-size convex
subset of points can be computed by a randomized algorithm in
$\mathcal{O}(n\log{n})$ expected time.

###### keywords:

Erdős-Szekeres theorem, Horton set, Valtr grid, Conlon-Lim grid, density-
restricted set, spread of a set, approximation algorithm, randomized algorithm

##  1 Introduction

A set of points in the $d$-dimensional space $\mathbb{R}^{d}$ is said to be:
(i) in _general position_ if any $d+1$ or fewer points are _affinely
independent_ ; and (ii) in _convex position_ if none of the points lies in the
convex hull of the other points.

In $1935$ Erdős and Szekeres proved, as one of the first Ramsey-type results
in combinatorial geometry, that for every $n\in\mathbb{N}$, a sufficiently
large point set in the plane in general position contains $n$ points in convex
position [20]. The minimum cardinality of a point set that contains a subset
of $n$ points in convex position is known as the Erdős–Szekeres number,
denoted here by $f(n)$. The resulting upper bound in their paper was
$f(n)\leq\binom{2n-4}{n-2}+1=4^{n(1-o(1))}$. In $1960$, the same authors
showed a construction that implies a lower bound of $f(n)\geq 2^{n-2}+1$, and
conjectured that this lower bound is tight [21]. The current best (asymptotic)
upper bound, due to Suk [35], is $f(n)\leq 2^{n(1+o(1))}$. In other words,
every set of $n$ points in general position in the plane contains
$(1-o(1))\log{n}$ points in convex position, and this bound is tight up to
lower-order terms.

Let $A$ be a set of $n$ points in general position in $\mathbb{R}^{d}$. Define

$\Delta(A)=\frac{\max\\{{\rm dist}(a,b):a,b\in A,a\neq b\\}}{\min\\{{\rm
dist}(a,b):a,b\in A,a\neq b\\}},$

where ${\rm dist}(a,b)$ is the Euclidean distance between points $a$ and $b$.
The ratio $\Delta(A)$ is referred to as the _aspect ratio_ or the _spread_ of
$A$; see for instance [12, 17]. We assume without loss of generality that the
minimum pairwise distance is $1$ and in this case $\Delta(A)$ is the diameter
of $A$. A standard volume argument shows that if $A$ has $n$ points, then
$\Delta(A)\geq c_{d}\,n^{1/d}$, where $c_{d}>0$ is a constant depending only
on $d$; for instance it is known [36] that $c_{2}\geq
2^{1/2}3^{1/4}\pi^{-1/2}\approx 1.05$. On the other hand, the section of the
integer lattice $[n]^{d}$ shows that this bound is tight up to the
aforementioned constant. A point set satisfying the condition
$\Delta(A)=\mathcal{O}(n^{1/d})$, is called here _density-restricted_ (or
simply _dense_ , see for instance [19, 28, 37]).

In the seminal article of Erdős and Szekeres [20], the constructed point sets
with no large subsets in convex position have very large spread. Similarly, in
Horton’s seminal article on point sets with no empty convex heptagons, the
constructed point sets also have very large spread (Horton sets will be
discussed in Section 2.) Answering the emerging question of whether such
results really require large spreads, Valtr [36] showed the existence of
arbitrarily large planar sets $A$ with $\Delta(A)\leq\alpha n^{1/2}$ that have
no empty convex heptagons. (Observe that whenever $\Delta(A)$ satisfies this
condition, we have $\alpha\geq c_{2}$.) This property can be achieved for
example by a suitable, carefully crafted, small perturbation of the lattice
section $[n]^{2}$. Moreover, Valtr [36] obtained by probabilistic arguments
the following result:

######  Theorem 1.1.

(Valtr [36]) For every $\alpha>0$ there exists $\beta=\beta(\alpha)>0$ such
that any set of $n$ points in general position in the plane satisfying
$\Delta(A)\leq\alpha n^{1/2}$, contains a subset of $\beta n^{1/3}$ points in
convex position.

It is therefore apparent that the size of the largest convex subset contained
in an $n$-element point set strongly depends on the spread of the set. In the
same paper, Valtr generalized Theorem 1.1 to a broader range of the spread (by
similar arguments):

######  Theorem 1.2.

(Valtr [36]) For every $\alpha>0$ and
$\tau\in\left[\frac{1}{2},\frac{3}{4}\right)$, there exists
$\beta=\beta(\alpha,\tau)>0$ such that any set $A$ of $n$ points in general
position in the plane satisfying $\Delta(A)\leq\alpha n^{\tau}$ contains a
subset of $\beta n^{1-4\tau/3}$ points in convex position.

On the other hand, as remarked by Valtr, the construction by Erdős and
Szekeres [21] can be transformed into one with spread $\Delta<n$ and with at
most $\log{n}+2$ points in convex position. For the remaining range
$\tau\in\left[\frac{3}{4},1\right)$, Valtr stated in his PhD Thesis [37]
(without proof) that an involved argument shows that any set $A$ of $n$ points
in general position in the plane satisfying $\Delta(A)\leq\alpha n^{\tau}$
(where $\alpha>0$ is a constant) contains a convex subset of size $\beta
n^{\varepsilon}$ for some $\varepsilon=\varepsilon(\tau)>0$. We will return to
this question in Section 6.

For density-restricted sets, the previously mentioned small perturbation of
the lattice section $[n]^{2}$ provides a matching upper bound:

######  Theorem 1.3.

(Valtr [36]) For every $n\in\mathbb{N}$ there exists an $n$-element point set
$A\subset\mathbb{R}^{2}$ in general position, satisfying $\Delta(A)\leq\alpha
n^{1/2}$, for some constant $\alpha>0$, in which every subset in convex
position has at most $\mathcal{O}(n^{1/3})$ points.

For a positive integer $n$, let $\gamma_{d}(n)$ denote the largest integer
such that any set $A$ of $n$ points in general position in $\mathbb{R}^{d}$,
satisfying $\Delta(A)\leq\alpha n^{1/d}$ for a fixed $\alpha>0$, contains at
least $\gamma_{d}(n)$ points in convex position. In these terms, Valtr’s
result is that $\gamma_{2}(n)=\Theta(n^{1/3})$. The estimation of
$\gamma_{d}(n)$ for $d\geq 3$ has remained an open problem. Here we continue
this line of research in three dimensions and prove that
$\gamma_{3}(n)=\Theta(n^{1/2})$.

Our Results.

######  Theorem 1.4.

For every $\alpha>0$ there exists $\beta(\alpha)>0$ such that any set of $n$
points in $\mathbb{R}^{3}$ in general position, satisfying
$\Delta(A)\leq\alpha n^{1/3}$, contains a subset of at least $\beta n^{1/2}$
points in convex position. In particular, $\gamma_{3}(n)=\Omega(n^{1/2})$.

######  Theorem 1.5.

For every $\alpha>0$ and $\tau\in\left[\frac{1}{3},\frac{2}{3}\right)$, there
exists $\beta=\beta(\alpha,\tau)>0$ such that any set $A$ of $n$ points in
general position in $\mathbb{R}^{3}$ satisfying $\Delta(A)\leq\alpha n^{\tau}$
contains a subset of $\beta n^{1-3\tau/2}$ points in convex position.

######  Theorem 1.6.

For every $n\in\mathbb{N}$ there exists an $n$-element point set
$A\subset\mathbb{R}^{3}$ in general position, satisfying $\Delta(A)\leq\alpha
n^{1/3}$, for some constant $\alpha>0$, in which every subset in convex
position has at most $\mathcal{O}(n^{1/2})$ points. In particular,
$\gamma_{3}(n)=\mathcal{O}(n^{1/2})$.

######  Theorem 1.7.

Given any $n$-element point set $A\subset\mathbb{R}^{3}$ in general position,
satisfying $\Delta(A)\leq\alpha n^{1/3}$ for a fixed $\alpha$, a
$\Omega(n^{-1/6})$-factor approximation of the maximum-size convex subset of
points can be computed by a randomized algorithm in $\mathcal{O}(n\log{n})$
expected time.

In 1960, Erdős and Szekeres [21] constructed for every positive integer $k$, a
set of $n:=2^{k}$ points in general position in the plane, such that the size
of the largest convex subset is $k-1=\log{n}-1$. In 2017, Duque, Fabila-
Monroy, and Hidalgo-Toscano [18] showed how to realize that construction on an
integer grid of size $\mathcal{O}(n^{2}\log^{3}{n})$. In 1978, Erdős asked
whether, given any positive integer $k$, every sufficiently large point set in
general position in the plane contains $k$ points in convex position such that
the respective polygon is empty of other points. In 1983, Horton [25] gave a
negative answer by constructing arbitrarily large point sets with no empty
convex $7$-gon. Such sets are generally called Horton sets. In 2017, Barba,
Duque, Fabila-Monroy, and Hidalgo-Toscano [11] showed how to realize a Horton
set of size $n$ on an integer grid of size
$\mathcal{O}(n^{\frac{1}{2}\log{(n/2)}})$. On the other hand, they proved that
any set of $n$ points with integer coordinates combinatorially equivalent to a
Horton set contains a point with a coordinate at least
$\Omega(n^{\frac{1}{24}\log{(n/2)}})$.

Given a point set in general position in $\mathbb{R}^{d}$, the problem of
computing a maximum-size subset in convex position can be solved in polynomial
time for $d=2$ by the dynamic programming algorithm of Chvátal and Klincsek
[16]; their algorithm runs in $\mathcal{O}(n^{3})$ time. In contrast, the
general problem in $\mathbb{R}^{d}$ was shown to be NP-complete for every
$d\geq 3$ by Giannopoulos, Knauer, and Werner [23].

Several problems concerning convex polygons (resp., polytopes) whose vertices
lie in a Cartesian product of two (resp., $d$) sets of reals have been
recently studied in [15]. See also [13, Sec. 8.2] for additional problems
related to Horton sets and the Erdős-Szekeres theorem. A comprehensive survey
on the Erdős–Szekeres problem is due to Morris and Soltan [31].

Recently, Bukh and Dong [14] independently proved that
$\gamma_{d}=\Theta_{d}(n^{(d-1)/(d+1)})$ for all $d\in\mathbb{N}$, using more
or less different techniques.

Definitions and notations. For a finite point set $S\subset\mathbb{R}^{d}$,
let $g(S)=g_{d}(S)$ be the maximum size of a convex subset of $S$; when there
is no confusion, the subscript $d$ may be omitted. Let $g(n)$ be defined as

$g(n)=\min\\{g(S)\colon|S|=n,S\text{ is in general position}\\}.$

The _interior_ and the _boundary_ of a set $S\subset\mathbb{R}^{d}$ are
denoted by ${\rm Int}(S)$ and $\partial S$, respectively. A vector in
$\vec{v}=(x_{1},\ldots,x_{d})\in\mathbb{Z}^{d}$ is _primitive_ if
$\gcd(x_{1},\ldots,x_{k})=1$. Let $[n]$ denote the set $\\{1,2,\ldots,n\\}$.
Unless specified otherwise, all logarithms are in base $2$.

Here we use the convention that the approximation ratio of an algorithm is
$<1$ for a maximization problem and $>1$ for a minimization problem (as in
[39]). We frequently write $\mathcal{O}_{d}$, when needed, to indicate that
the hidden constant in the $\mathcal{O}$ asymptotic notation depends only on
$d$.

##  2 Preliminaries

A set of points in the plane $\\{p_{i}=(x_{i},y_{i}),i=1,\ldots,n\\}$ is in
_strong general position_ if it is in general position and no two $x$\- or
$y$-coordinates are the same. More generally, a set of points
$P\subset\mathbb{R}^{d}$ $\\{p_{i},i=1,\ldots,n\\}$ is said to be in _strong
general position_ if $P$ is in general position and no two values of the $j$th
coordinate are the same, for $j=1,\ldots,d$. For any
$f\in\\{0,1,\ldots,d-1\\}$, denote by $\pi_{f}$ the orthogonal projection from
$\mathbb{R}^{d}$ onto $\mathbb{R}^{f}$ obtained by retaining the first $f$
coordinates.

Let $A,B\subset\mathbb{R}^{d}$ be finite sets such that $A\cup B$ is in strong
general position in $\mathbb{R}^{d}$. We say that $A$ lies _deep below_ $B$
(equivalently, $B$ lies _high above_ $A$) if the following holds: every point
in $A$ lies below all hyperplanes determined by $d$ points in $B$ and every
point in $B$ lies above all hyperplanes determined by $d$ points in $A$
(w.r.t. the $d$th coordinate) [29, Ch. 3.2]. Whenever needed, we extend this
relation to apply to any coordinate other than the last one.

Let $X\subset\mathbb{R}^{d}$ be a finite set in general position. A
$k$-element set $Y\subseteq X$ is called a _$k$ -hole_ in $X$ if $Y$ is in
convex position and ${\rm conv}(Y)\cap X=Y$ [29, Ch. 3.2]. In the plane
($d=2$), $Y$ is the vertex set of a convex polygon with no point of $X$
inside. Horton [25], answering a question by Erdős, constructed arbitrary
large finite sets without a $7$-hole. On the other hand, every sufficiently
large finite set in general position contains six points that determine a
$6$-hole (i.e., an empty convex hexagon); this was shown about 25 years later
by Gerken [22] and respectively Nicolás [32].

Horton sets and Valtr grids in the plane. For a sequence of points sorted by
$x$-coordinates (with no duplicate $x$-coordinates)
$P=\\{p_{1},p_{2},\ldots,p_{n}\\}$, let $P_{0}=\\{p_{2},p_{4},\ldots\\}$
denote the subsequence of points with even indexes and
$P_{1}=\\{p_{1},p_{3},\ldots\\}$ denote the subsequence of points with odd
indexes. A finite set $H$ is a _Horton set_ if either (i) $|H|=1$, or (ii)
$|H|\geq 2$, both $H_{0}$ and $H_{1}$ are Horton sets and one of these two
sets lies deep below the other one.

The above definition allows one to construct inductively Horton sets in the
plane of any size; see [29, Ch.3.2]. Following [17, 25, 36], one can construct
Horton sets as follows. For a nonnegative integer $N$, let its binary
representation be $N=\sum_{i\geq 0}a_{i}2^{i}$, where $a_{i}\in\\{0,1\\}$. For
any positive $0<\varepsilon<1/2$, denote by $(N)_{\varepsilon}$ the real
number

$(N)_{\varepsilon}=\sum_{i\geq 0}a_{i}\varepsilon^{i+1},$ (1)

and note that $0<(N)_{\varepsilon}<2\varepsilon$. Then the set
$S=\\{p_{i}:i\in[n]\\},\text{ where }p_{i}=(i,(i)_{\varepsilon})$, is a Horton
set. Indeed, $S_{0}$ lies deep below $S_{1}$ if $\varepsilon$ is sufficiently
small, and further on, this property holds recursively for the smaller sets
$S_{0}$ and $S_{1}$.

Interestingly enough, Valtr [36] showed how to use multiple Horton sets to
obtain planar sets that are sufficiently small perturbations of a lattice
section $[n]^{2}$ and that preserve the key property of the Horton set, namely
that of not containing any $7$-hole. The resulting sets (described in Theorem
1.3) are not Horton sets per se.

Higher dimensions. Recently, Conlon and Lim [17] extended Valtr’s planar
construction to higher dimensions such that the resulting sets do not contain
large holes (i.e., convex polytopes with a large number of vertices that are
empty of points from the set). Their result is summarized in Theorem 2.1.

######  Theorem 2.1.

(Conlon and Lim [17]) For any integers $n\geq 1$ and $d\geq 2$ and any
$\varepsilon>0$, there exists an integer $C_{d}=d^{\mathcal{O}(d^{3})}$ and a
set of points $\\{P_{\vec{x}}\mid\vec{x}\in[n]^{d}\\}\subset\mathbb{R}^{d}$
that is $C_{d}$-hole-free and satisfies ${\rm
dist}(P_{\vec{x}},\vec{x})\leq\varepsilon$ for all $\vec{x}\in[n]^{d}$.

Both the _Valtr grid_ [36] and the _Conlon-Lim grid_ [17] can be described in
terms of negligible perturbations (or negligible functions). Given two finite
sets $A,B\subset\mathbb{R}^{d}$, a bijection $f\colon A\to B$ is _negligible_
if, whenever $S\subset A$ and $x\in A$ with $x\in{\rm Int}({\rm conv}(S))$,
then $f(x)\in{\rm Int}({\rm conv}(f(S)))$.

The planar construction can be described in one paragraph as follows (we
mainly follow here the outline of Conlon and Lim [17]). Starting with the
lattice section $S_{0}=[n]^{2}$, each column of points is shifted vertically
by a small positive amount (i.e., negligible perturbation), resulting in a set
$S_{1}$. The shifting is done in such a way that each row of points is a
Horton set. This also implies that any nonvertical line of lattice points
yields a subset of $S_{1}$ that is a Horton set. Finally, each row of points
is shifted horizontally by an even smaller positive amount to get $S_{2}=S$ so
that each column of points is a Horton set. Overall, every line of lattice
points in $S_{0}$ corresponds to a Horton set in $S_{2}$. In other words, $S$
is the Minkowski sum of two Horton sets, one of them resembling $[n]$ along
the $x$-axis and the other along the $y$-axis. It is easy to adjust the two
perturbations if needed so that the final set $S$ is in strongly general
position. It is worth noting that the final set $S$ is _not_ a Horton set by
itself.

Number of vertices and faces. The number of vertices of a convex lattice
polytope can be bounded from above using a theorem by Andrews [6].

######  Theorem 2.2.

(Andrews [6]; see also [9, 10, 33]) For every finite set
$S\subset\mathbb{Z}^{d}$, $d\geq 2$, the lattice polytope ${\rm conv}(S)$ has
$\mathcal{O}_{d}\left(V^{\frac{d-1}{d+1}}\right)$ vertices, where $V={\rm
Vol}({\rm conv}(S))>0$.

The same bound holds for the total number of faces of the lattice polytope
${\rm conv}(S)$.

######  Theorem 2.3.

([7, Theorem 3.2] see also [8, 27]) For every finite set
$S\subset\mathbb{Z}^{d}$, $d\geq 2$, the lattice polytope ${\rm conv}(S)$ has
$\mathcal{O}_{d}\left(V^{\frac{d-1}{d+1}}\right)$ faces (of any dimension),
where $V={\rm Vol}({\rm conv}(S))>0$.

We generalize Theorem 2.2 in the plane in another direction, as follows. This
technical tool will be used in Section 4.

######  Lemma 2.4.

For every finite set $S\subset\mathbb{Z}^{2}$ and for every integer $t$,
$1\leq t\leq\sqrt{A}$, the lattice polygon ${\rm conv}(S)$ has
$\mathcal{O}\left((A/t^{2})^{1/3}\right)$ edges that contain more than $t$
points in $\mathbb{Z}^{2}$, where $A={\rm Area}({\rm conv}(S))>0$.

######  Proof 2.5.

For brevity, let $P={\rm conv}(S)$. The boundary of $P$ can be decomposed into
two $x$-monotone polygonal chains, a lower arc $P_{1}$ and an upper arc
$P_{2}$. It suffices to show that $P_{1}$ and $P_{2}$ each have
$\mathcal{O}((A/t^{2})^{1/3})$ edges that contain more than $t$ grid points.

Consider $P_{1}$ (the argument for $P_{2}$ is analogous and omitted). Suppose
that $P_{1}$ has $L_{1}$ edges that contain more than $t$ grid points. Denote
the vertex set of $P_{1}$ as $S_{1}=\\{v_{0},v_{1},\ldots,v_{k}\\}$, labeled
in left-to-right order, and assume that $v_{0}$ is the origin. Note that
$S_{1}\subset S$, and so ${\rm Area}({\rm conv}(S_{1}))\leq{\rm Area}({\rm
conv}(S))=A$. For $i=1,\ldots,k$, if the edge $v_{i-1}v_{i}$ contains $m_{i}$
grid points, then $v_{i}-v_{i-1}=(m_{i}-1)\vec{e}_{i}$ for a primitive vector
$\vec{e}_{i}$. For every $i=1,\ldots,k$, let $m_{i}^{\prime}$ be the largest
multiple of $t$ such that $0\leq m_{i}^{\prime}\leq m_{i}-1$. Note that if
$m_{i}\leq t$ then $m^{\prime}_{i}=0$.

Let $S^{\prime}_{1}$ be the vertex set of the polygonal arc obtained by
concatenating the vectors
$m_{1}^{\prime}\vec{e}_{1},\ldots,m_{k}^{\prime}\vec{e}_{k}$. Since
$m_{i}^{\prime}\leq m_{i}$ for all $i$, then ${\rm Area}({\rm
conv}(S_{1}^{\prime}))\leq{\rm Area}({\rm conv}(S_{1}))\leq A$. By
construction, we have $S_{1}^{\prime}\subset t\,\mathbb{Z}^{2}$, hence
$S^{\prime\prime}_{1}:=\frac{1}{t}\,S_{1}^{\prime}\subset\mathbb{Z}^{2}$. Thus
${\rm conv}(S_{1}^{\prime\prime})$ is a lattice polygon of area at most
$A/t^{2}$. If ${\rm conv}(S_{1}^{\prime\prime})$ has positive area, then
Theorem 2.2 applies, otherwise $L_{1}\leq 2$. In both cases, ${\rm
conv}(S_{1}^{\prime\prime})$ has $L_{1}=\mathcal{O}((A/t^{2})^{1/3})$
vertices, as required.

##  3 Lower bound: Proof of Theorem 1.4

Let $A$ be a set of $n$ points in $\mathbb{R}^{3}$ in general position,
satisfying $\Delta(A)\leq\alpha n^{1/3}$. We may assume that $A\subset B$,
where $B$ is a ball of radius $R=\alpha n^{1/3}$ centered at $O$; see Fig. 1
(left). Consider any maximal packing $\mathcal{P}$ of spherical caps of height
$h=\alpha n^{-1/6}$ and radius $r=(R^{2}-(R-h)^{2})^{1/2}=\Theta(\alpha
n^{1/12})$. For instance, $\mathcal{P}$ may be constructed greedily from an
empty packing by successively adding spherical caps that do not intersect
previous caps.

Figure 1: Left: Elements of a spherical cap: the radius of the sphere $R$, the
radius of the base of the cap $r$, the center $p$ of the cap, the height of
the cap $h$, and the polar angle $\gamma$. Right: Concentric balls and the
placement of $C$.

######  Lemma 3.1.

The spherical caps in $\mathcal{P}$ cover at least one quarter of the surface
area of $B$.

######  Proof 3.2.

Consider the set $\mathcal{P}^{\prime}$ of enlarged caps with the same centers
as in $\mathcal{P}$ but with double polar angle. Due to the maximality of
$\mathcal{P}$, the caps in $\mathcal{P}^{\prime}$ cover the surface $\partial
B$ of $B$. Indeed, if there is an uncovered point $p\in\partial B$, then the
cap of spherical radius $r$ centered at $p$ would not intersect any cap in
$\mathcal{P}$, contradicting the maximality of $\mathcal{P}$. Doubling the
polar angle of a spherical cap increases its area by a factor of at most 4.
Consequently, the surface area of the union of spherical caps in
$\mathcal{P}^{\prime}$ is less than four times the surface area covered by
$\mathcal{P}$. Since $\mathcal{P}^{\prime}$ covers $\partial B$, then the caps
in $\mathcal{P}$ cover at least one quarter of the surface area of $B$.

Since the area of $\partial B$ is $4\pi R^{2}$ and the area of each spherical
cap in $\mathcal{P}$ is $2\pi Rh$, the cardinality of $\mathcal{P}$ is bounded
from below (by Lemma 3.1) as follows:

$|\mathcal{P}|\geq\frac{4\pi R^{2}}{4\cdot 2\pi
Rh}=\frac{R}{2h}=\frac{n^{1/2}}{2}.$ (2)

Label these caps as $\Psi_{i}$, $i=1,\ldots,|\mathcal{P}|$, in an arbitrary
fashion. The following is analogous with Lemma 2.2 in [36], however, due to
the specifics of our construction, its proof is obvious.

######  Lemma 3.3.

If we choose at most one point from each of the spherical caps $\Psi_{i}$,
$i=1,\ldots,|\mathcal{P}|$, then the chosen points are in convex position.

We wish to find a suitable placement of a ball $C$ congruent to $B$ (in a
rotated position) so that a constant fraction of its spherical caps in
$\mathcal{P}$ contains some points from $A$. This would prove Theorem 1.4. As
in Valtr’s work, we proceed by probabilistic methods; the resulting algorithm
is randomized.

Let $\mathcal{S}$ be the (infinite) set of all spherical caps of radius $r$
and height $h$ corresponding to all balls $C$ congruent to $B$ contained in a
ball $B^{\prime\prime}$ concentric with $B$ of radius $3R$ centered at $O$;
note that any such ball $C$ is centered in a ball $B^{\prime}$ concentric with
$B$ of radius $2R$ centered at $O$. Refer to Fig. 1 (right). A spherical cap
in $\mathcal{S}$ is determined by two parameters: (1) the _direction_ , which
is a unit vector in $\mathbb{S}^{2}$ parallel to the vector from the center of
the corresponding ball $C$ to the center of the cap; and (2) the center of the
corresponding ball $C$, which is in $B^{\prime}$. Consequently, $\mathcal{S}$
is parameterized by the Cartesian product $\mathbb{S}^{2}\times B^{\prime}$;
and the Lebesgue measures on $B^{\prime}$ and $\mathbb{S}^{2}$, resp., induce
a product measure $\mu$ on $\mathcal{S}$. Since we have ${\rm
Vol}(B^{\prime})=\frac{4\pi}{3}(2R)^{3}=\frac{32}{3}\pi R^{3}$ and ${\rm
Area}(\mathbb{S}^{2})=4\pi^{2}$, then $\mu(\mathcal{S})$ has a simple formula:

$\mu(\mathcal{S})=\frac{128}{3}\pi^{3}R^{3}.$ (3)

A key lemma (analogous to Lemma 2.3 in [36]) is the following.

######  Lemma 3.4.

There exists a positive constant $c=c(\alpha)$ such that

$\mu(\\{S\in\mathcal{S}\colon S\cap A\neq\emptyset\\})\geq c\mu(\mathcal{S}).$

Its proof relies on two lemmas (analogous to Lemmas 2.4 and 2.5 in [36]).

######  Lemma 3.5.

Let $a\in A$ and for every $j\in\mathbb{N}$ let $A(j)$ be the set of points
$a^{\prime}\in A$ such that $j\leq{\rm dist}(a,a^{\prime})\leq j+1$. Then
$|A(j)|\leq c_{1}j^{2}$, for some constant $c_{1}>0$.

######  Proof 3.6.

Draw $\mathcal{O}(j^{2})$ planes incident to $a$ that divide the surface of
the ball of radius $j+1$ centered at $a$ into $\mathcal{O}(j^{2})$ surface
patches of diameter at most $1/2$. The three concentric spheres of radii $j$,
$j+1/2$, and $j+1$ together with the $\mathcal{O}(j^{2})$ planes partition the
set $A(j)$ into $\mathcal{O}(j^{2})$ $3$-dimensional cells of diameter less
than $1$. As such, each cell contains at most one point from $A$ and the lemma
follows.

For every point $a\in A$, and every integer $i=0,1,\ldots,n$, we introduce the
notation

$\displaystyle\mathcal{S}(a)$ $\displaystyle=\\{S\in\mathcal{S}\colon a\in
S\\},$ $\displaystyle\mathcal{S}_{i}$
$\displaystyle=\\{S\in\mathcal{S}\colon|S\cap A|=i\\},$ $\displaystyle m_{i}$
$\displaystyle=\mu(\mathcal{S}_{i}).$

######  Lemma 3.7.

The locus of directions $\vec{v}\in\mathbb{S}^{2}$ corresponding to spherical
caps in $\mathcal{S}(a)\cap\mathcal{S}(a^{\prime})$ is contained in a
spherical ring of polar angle $\theta$, where $\theta/2=\arcsin\frac{h}{{\rm
dist}(a,a^{\prime})}$; see Fig. 2.

Figure 2: A point pair $a,a^{\prime}\in A$ in a spherical cap of direction
$\vec{v}$; and a spherical ring of angle $\theta$.

######  Proof 3.8.

Let $\Psi$ be a spherical cap in $\mathcal{S}(a)\cap\mathcal{S}(a^{\prime})$
and let $p$ denote its center. We distinguish between two cases.

_Case 1._ $1\leq{\rm dist}(a,a^{\prime})\leq\sqrt{r^{2}+h^{2}}$. In an
extremal position, $a^{\prime}=p$ and $a$ is on the base of the cap. Refer to
Fig. 3 (left). The locus of directions $\vec{v}\in\mathbb{S}^{2}$
corresponding to spherical caps in $\mathcal{S}(a)\cap\mathcal{S}(a^{\prime})$
is a spherical ring of polar angle $\theta$, where
$\theta/2=\arcsin\frac{h}{{\rm dist}(a,a^{\prime})}$.

Figure 3: Extremal positions of a segment that fits into the cap in Case 1
(left) and Case 2 (right).

_Case 2._ $\sqrt{r^{2}+h^{2}}<{\rm dist}(a,a^{\prime})\leq 2r$. In an extremal
position, $a$ is on the circle at the base of the cap, $a^{\prime}$ is on the
surface of the cap, and the great circle incident to $a$ and $a^{\prime}$
passes through $p$; see Fig. 3 (right). The locus of directions
$\vec{v}\in\mathbb{S}^{2}$ corresponding to spherical caps in
$\mathcal{S}(a)\cap\mathcal{S}(a^{\prime})$ is a spherical ring of polar angle
$\theta^{\prime}$, where $\theta^{\prime}/2=\arcsin\frac{y}{{\rm
dist}(a,a^{\prime})}\leq\arcsin\frac{h}{{\rm dist}(a,a^{\prime})}$, and $y$ is
the distance between $a^{\prime}$ and the base of $\Psi$. Consequently, this
locus is contained in a spherical ring of polar angle $\theta$, where
$\theta/2=\arcsin\frac{h}{{\rm dist}(a,a^{\prime})}$. In particular, observe
that when ${\rm dist}(a,a^{\prime})=2r$, then $y=\theta^{\prime}=0$.

######  Lemma 3.9.

There exist positive constants $c_{2}$, $c_{3}$, and $c_{4}$ such that:

  1. (i)

$\forall a\in A\colon c_{2}\leq\mu(\mathcal{S}(a))\leq c_{3}$, and

  2. (ii)

$\forall a\in A\colon\sum_{a^{\prime}\in
A}\mu(\mathcal{S}(a)\cap\mathcal{S}(a^{\prime}))\leq c_{4}$.

######  Proof 3.10.

(i) The centers of spherical caps $S\in\mathcal{S}(a)$ with a fixed direction
$\vec{v}\in\mathbb{S}^{2}$ form a congruent spherical cap of the same
direction $\vec{v}$. Hence $\mu(\mathcal{S}(a))=v_{0}\cdot{\rm
Area}(\mathbb{S}^{2})$, where $v_{0}=\frac{\pi
h^{2}}{3}(3R-h)=\pi\alpha^{3}(1-n^{-1/2}/3)$ is the volume of a spherical cap.
Since $1-n^{-1/2}/3\geq 5/6$ for $n\geq 4$, and ${\rm
Area}(\mathbb{S}^{2})=4\pi^{2}$, we deduce that
$c_{2}\leq\mu(\mathcal{S}(a))\leq c_{3}$, for constants
$c_{2}=\pi\alpha^{3}\cdot\frac{5}{6}\cdot 4\pi^{2}$ and
$c_{3}=\pi\alpha^{3}\cdot 4\pi^{2}$.

(ii) For $a,a^{\prime}\in A$, let $W_{a,a^{\prime}}$ be the locus of
directions $\vec{v}\in\mathbb{S}^{2}$ corresponding to spherical caps in
$\mathcal{S}(a)\cap\mathcal{S}(a^{\prime})$. Equivalently, for a fixed
spherical cap $S\in\mathcal{S}$ with direction vector
$\overrightarrow{aa^{\prime}}/{\rm dist}(a,a^{\prime})$, the set
$W_{a,a^{\prime}}$ is the locus of directions $\vec{v}\in\mathbb{S}^{2}$
corresponding to the line segments of length ${\rm dist}(a,a^{\prime})$
contained in $S$; see Fig. 2. Note that ${\rm dist}(a,a^{\prime})\geq 1$,
since the pairwise minimum distance is equal to $1$; and if ${\rm
dist}(a,a^{\prime})>2r$, then $W_{a,a^{\prime}}=\emptyset$, of measure 0. We
therefore have $1\leq{\rm dist}(a,a^{\prime})\leq 2r$. By Lemma 3.7,
$W_{a,a^{\prime}}$ is contained in a spherical ring of polar angle $\theta$,
where $\theta/2=\arcsin\frac{h}{{\rm dist}(a,a^{\prime})}$, and so its measure
in $\mathbb{S}^{2}$ is $\mathcal{O}(\arcsin(h/{\rm
dist}(a,a^{\prime}))=\mathcal{O}(h/{\rm dist}(a,a^{\prime}))$. Since the
spherical caps from $\mathcal{S}(a)\cap\mathcal{S}(a^{\prime})$ are in
$\mathcal{S}(a)$, we have

$\mu(\mathcal{S}(a)\cap\mathcal{S}(a^{\prime}))\leq c_{5}\,\frac{h}{{\rm
dist}(a,a^{\prime})},$ (4)

for some constant $c_{5}>0$. Recall that $A(j)=\\{a^{\prime}\in A:j\leq{\rm
dist}(a,a^{\prime})\leq j+1\\}$. Hence

$\displaystyle\sum_{a^{\prime}\in
A}\mu(\mathcal{S}(a)\cap\mathcal{S}(a^{\prime}))$
$\displaystyle=\mu(\mathcal{S}(a))+\sum_{j=1}^{\lfloor
2r\rfloor}\sum_{a^{\prime}\in
A(j)}\mu(\mathcal{S}(a)\cap\mathcal{S}(a^{\prime}))$ $\displaystyle\leq
c_{3}+\sum_{j=1}^{\lfloor 2r\rfloor}\sum_{a^{\prime}\in A(j)}c_{5}hj^{-1}\leq
c_{3}+\sum_{j=1}^{\lfloor 2r\rfloor}c_{1}j^{2}c_{5}hj^{-1}$ $\displaystyle\leq
c_{3}+c_{1}c_{5}h\sum_{j=1}^{\lfloor 2r\rfloor}j\leq
c_{3}+3c_{1}c_{5}r^{2}h\leq c_{3}+6c_{1}c_{5}\alpha^{3}=c_{4},$

for some constant $c_{4}>0$. Here we used part (i), Inequality (4), Lemma 3.5,
and $r^{2}h<2\alpha^{3}$.

Proof of Lemma 3.4. We wish to bound $\sum_{i=1}^{n}m_{i}$ from below.
Consider the sums $\sum_{i=1}^{n}m_{i}$ and $\sum_{i=1}^{n}i^{2}m_{i}$ for
which we apply the Cauchy-Schwarz inequality in the following form:

$\left(\sum_{i=1}^{n}m_{i}\right)\left(\sum_{i=1}^{n}i^{2}m_{i}\right)\geq\left(\sum_{i=1}^{n}im_{i}\right)^{2}.$

We can bound $\sum_{i=1}^{n}im_{i}$ from below and $\sum_{i=1}^{n}i^{2}m_{i}$
from above as follows:

$\displaystyle\sum_{i=1}^{n}im_{i}$ $\displaystyle=\sum_{a\in
A}\mu(\mathcal{S}(a))\geq\sum_{a\in A}c_{2}=c_{2}\,n,$ [by Lemma 3.9(i)]
$\displaystyle\sum_{i=1}^{n}i^{2}m_{i}$ $\displaystyle=\sum_{a\in
A}\sum_{a^{\prime}\in
A}\mu(\mathcal{S}(a)\cap\mathcal{S}(a^{\prime}))\leq\sum_{a\in
A}c_{4}=c_{4}\,n.$ [by Lemma 3.9(ii)]

Applying these estimates yields the desired lower bound

$\sum_{i=1}^{n}m_{i}\geq\frac{\left(\sum_{i=1}^{n}im_{i}\right)^{2}}{\sum_{i=1}^{n}i^{2}m_{i}}\geq\frac{(c_{2}\,n)^{2}}{c_{4}\,n}=\frac{c_{2}^{2}}{c_{4}}\,n.$

Consequently,

$\frac{\mu(\\{S\in\mathcal{S}\colon S\cap
A\neq\emptyset\\})}{\mu(\mathcal{S})}=\frac{\sum_{i=1}^{n}m_{i}}{\mu(\mathcal{S})}\geq\frac{(c_{2}^{2}/c_{4})n}{\frac{128}{3}\pi^{3}\alpha^{3}n}=c>0,$

for some positive constant $c$. ∎

Proof of Theorem 1.4. We randomly place a ball $C$ congruent to $B$ inside
$B^{\prime}$. Specifically, recall that $B$, $B^{\prime}$, and
$B^{\prime\prime}$ are concentric balls of radii $R$, $2R$, and $3R$,
respectively, where $A\subset B\subset B^{\prime}\subset B^{\prime\prime}$. We
construct a random congruence as follows: Let $\varrho$ be rotation in
$\mathrm{SO}(3)$, the group of rotation in $\mathbb{R}^{3}$, chosen uniformly
at random; and let $\tau$ be a translation that maps $O$ to point in
$B^{\prime}$ chosen uniformly at random. Put $\Phi:=\tau\circ\varrho$, and
$C:=\Phi(B)$. Since the center of $C$ is in $B^{\prime}$, then $C\subset
B^{\prime\prime}$. For any spherical cap $S_{0}\in\mathcal{P}$ of direction
$\vec{v}\in\mathbb{S}^{2}$, the direction $\varrho(\vec{v})$ is distributed
uniformly on $\mathbb{S}^{2}$ [30]. Consequently, the probability distribution
of the indicator variable $I[\Phi(S_{0})=S]$ over $S\in\mathcal{S}$ is a
scalar multiple of $\mu$. By Lemma 3.9, $\Phi(S)$ contains some point in $A$
with a probability at least

$\frac{\mu(\\{S\in\mathcal{S}\colon S\cap
A\neq\emptyset\\})}{\mu(\mathcal{S})}\geq c,$

for some constant $c>0$. By linearity of expectation and (2), the expected
number of nonempty spherical caps in $\Phi(\mathcal{P})$ is at least
$\frac{1}{2}\,cn^{1/2}$. Setting $\beta=\frac{c}{2}$ completes the proof of
Theorem 1.4. ∎

Proof of Theorem 1.5 (sketch). Set $R=\alpha n^{\tau}$, $h=\alpha
n^{-\tau/2}$, $r=(R^{2}-(R-h)^{2})^{1/2}=\Theta(\alpha n^{\tau/4})$, and
proceed as in the proof of Theorem 1.4. With this setting we have
$r^{2}h=\Theta(\alpha^{3})$. The resulting lower bound is of the form

$\Omega\left(n^{1-3\tau}\,\frac{R^{2}}{r^{2}}\right)=\Omega\left(n^{1-3\tau/2}\right),$

as required. ∎

##  4 Upper bound: Proof of Theorem 1.6

In this section, we describe and analyze a $3$-dimensional construction,
similar to the Valtr and the Conlon-Lim grids. It suffices to prove Theorem
1.6 for every $n$ of the form $n=2^{3k}$, where $k\in\mathbb{N}$. Our point
set is a suitable perturbation of the $3$-dimensional Cartesian grid
$G=\\{0,1,\ldots,2^{k}-1\\}^{3}$, where each point lies within a ball of
radius $\mathcal{O}(\varepsilon)>0$ centered at an integer point in $G$. Here
$\varepsilon<10^{-2}2^{-k}<10^{-2}$ is a sufficiently small positive real that
depends on $n$. Recall that for a nonnegative integer $N=\sum_{i\geq
0}N_{i}2^{i}$, where $N_{i}\in\\{0,1\\}$, and for
$\varepsilon\in(0,\frac{1}{2})$, we have defined
$(N)_{\varepsilon}=\sum_{i\geq 0}N_{i}\varepsilon^{i+1}$. Note that
$0<(N)_{\varepsilon}<2\varepsilon$.

We give an explicit formula for the perturbation
$\Phi:G\rightarrow\mathbb{R}^{3}$ in terms of $\varepsilon>0$. Let
$\mathbf{e}_{1}$, $\mathbf{e}_{2}$, and $\mathbf{e}_{3}$ denote the three
standard basis vectors in $\mathbb{R}^{3}$. For a grid point $p\in G$, let
$p=(p_{1},p_{2},p_{3})$ denote the three coordinates of $p$. For all
$i,j\in\\{1,2,3\\}$, let $\varphi_{i,j}:G\rightarrow\mathbb{R}^{3}$,
$\varphi_{i,j}(p)=(p_{i})_{\varepsilon}\cdot\mathbf{e}_{j}$. For every
$p\in\mathbb{Z}^{3}$, let $\mathbf{u}(p)\in\mathbb{R}^{3}$ be a random unit
vector. We can now define the perturbation $\Phi:G\rightarrow\mathbb{R}^{3}$
as

$\displaystyle\Phi(p)$ $\displaystyle=p+\left(\sum_{i\neq
j}\varepsilon^{(3i+j-5)k}\cdot\varphi_{i,j}(p)\right)+\varepsilon^{7k}\cdot\mathbf{u}(p)$
(5)
$\displaystyle=\left(p_{1}+\varepsilon^{2k}(p_{2})_{\varepsilon}+\varepsilon^{5k}(p_{3})_{\varepsilon},p_{2}+(p_{1})_{\varepsilon}+\varepsilon^{6k}(p_{3})_{\varepsilon},p_{3}+\varepsilon^{k}(p_{1})_{\varepsilon}+\varepsilon^{4k}(p_{3})_{\varepsilon}\right)+\varepsilon^{7k}\mathbf{u}(p),$

and let $A=\Phi(G)$. The last term, $\varepsilon^{7k}\cdot\mathbf{u}(p)$,
ensures that $A$ is in strongly general position. It is convenient to think of
$\Phi$ as a concatenation of seven successive perturbations, corresponding to
the terms in (5). Terms with different powers of $\varepsilon$ ensure that
each successive perturbation is negligible with respect to previous
perturbations if $\varepsilon>0$ is sufficiently small. We introduce notation
for the result of the first perturbation: let
$\Phi_{1}:G\rightarrow\mathbb{R}^{3}$,
$\Phi_{1}(p)=p+\varphi_{1,2}(p)=\left(p_{1},p_{2}+(p_{1})_{\varepsilon},p_{3}\right)$.

We next analyze this construction and show that it contains no large convex
subsets as quantified in Theorem 1.6. Let $B\subset A$ be a set in convex
position, and let $C=\Phi^{-1}(B)$, i.e., $C\subset G$ with $B=\Phi(C)$. If
$\varepsilon>0$ is sufficiently small, then for every vertex $p$ of ${\rm
conv}(C)$, the point $\Phi(p)$ is a vertex of ${\rm conv}(B)$. However, for
every vertex $q$ of ${\rm conv}(B)$, the point $\Phi^{-1}(q)$ is either a
vertex of ${\rm conv}(C)$ or lies in the interior of an edge or a face of
${\rm conv}(C)$. We have

${\rm conv}(C)\subset{\rm conv}(G),\text{ and }{\rm Vol}({\rm
conv}(C))\leq{\rm Vol}({\rm conv}(G))=n.$

By Theorem 2.2, ${\rm conv}(C)$ has
$\mathcal{O}(n^{(3-1)/(3+1)})=\mathcal{O}(n^{1/2})$ vertices. By Euler’s
polyhedral formula, ${\rm conv}(C)$ has $\mathcal{O}(n^{1/2})$ edges and
facets. We will show that if an edge of ${\rm conv}(C)$ contains $m$ lattice
points in $G$, then only $\mathcal{O}(\log^{2}m)$ of these points are in $C$
(Lemma 4.3); and if a face $F$ of ${\rm conv}(C)$ contains $m$ lattice points
in $G$, then $\mathcal{O}(m^{1/3})$ of these points are in $C$ (Lemma 4.5).

We use three lemmas (Lemmas 4.1, 4.3, and 4.5). Lemma 4.1 describes the
subadditivity of the function $g(\cdot)$ (defined at the end of Section 1).
Its easy proof is left to the reader.

######  Lemma 4.1.

Let $S=\bigcup_{i=1}^{k}S_{i}$ be an arbitrary partition of $S$. Then
$g(S)\leq\sum_{i=1}^{k}g(S_{i})$.

Lemma 4.3 below states that in a perturbation of a set of collinear points in
the grid $G$, there are only $\mathcal{O}(\log^{2}n)$ points in convex
position. A possible proof for Lemma 4.3 would establish that the perturbation
of collinear points in $G$ is a Horton set in $\mathbb{R}^{3}$, and then apply
the following result due to Károlyi and Valtr [26].

######  Lemma 4.2.

(Károlyi and Valtr [26]) Let $S\in\mathbb{R}^{d}$ be a Horton set of size $n$.
Then $g_{d}(S)=\mathcal{O}(\log^{d-1}n)$, where the constant hidden in the
$\mathcal{O}$ notation depends only on $d$.

Instead, we give a direct proof for Lemma 4.3 and then generalize it to handle
a perturbation of a set of coplanar points in Lemma 4.5 below.

######  Lemma 4.3.

Let $S\subset G$ be a set of collinear points. Then ${\rm conv}(\Phi(S))$ has
$\mathcal{O}(\log^{2}m)$ vertices, where $m=|G\cap{\rm conv}(S)|$.

######  Proof 4.4.

We may assume that $|S|\geq 2$. Let $L$ be the line spanned by $S$, and let
$m=|G\cap{\rm conv}(S)|$. Consider the first coordinate axis ($x$-, $y$-, or
$z$-axis) that is not orthogonal to $L$. We give a detailed proof for the case
that the $x$-axis is not orthogonal to $L$. The other two cases are analogous
(and are omitted): If $L$ is orthogonal to the $x$-axis, then the first two
iterations of the perturbation (which depend on the first coordinate)
translate all points $S$ uniformly, hence they have no impact on the convex
hull of $\Phi(S)$. Similarly, if $L$ is orthogonal to both $x$\- and $y$-axes,
then we can ignore the components of the perturbation that depend on the first
and second coordinates (and use the third coordinate instead).

Assume that $L$ is not orthogonal to the $x$-axis. Label the points in $S$ as
$S=\\{s_{1},\ldots,s_{t}\\}$ sorted by increasing $x$-coordinates. Let the
binary representation of the $x$-coordinate of $s\in S$ be
$x(s)=\sum_{j=0}^{k-1}x_{j}(s)2^{j}$. We recursively define the sets

$S_{1}\supset S_{2}\supset\ldots\supset S_{b},$ (6)

for some suitable $b\leq\mathcal{O}(\log m)$ as follows; see Fig. 4. Let
$S_{1}=S$. Given a set $S_{a}\subset S$, for $a\geq 1$, with $|S_{a}|\geq 2$,
we define $S_{a+1}$ as follows. Let $j(a)\geq 0$ be the smallest integer such
that $\\{x_{j(a)}(s):s\in S_{a}\\}=\\{0,1\\}$; and let $S_{a+1}=\\{s\in
S_{a}:x_{j(a)}(s)=1\\}$. Importantly, this implies that the translation vector
$\varphi_{1,2}(s)$ has a term $\varepsilon^{j(a)}\mathbf{e}_{2}$ for all $s\in
S_{a+1}$; but this term is missing for all $s\in S_{a}\setminus S_{a+1}$. Note
that for all $s\in S_{a}$, the last (i.e., the least significant) $j(a)$ bits
in the binary expansion of $x(s)$ are the same. Consequently, $j(a+1)>j(a)$
for all $a\geq 1$; hence $a\leq\mathcal{O}(\log m)$, and the recursion
terminates with $b\leq\mathcal{O}(\log m)$, as claimed. Note also that
$|S_{b}|=1$ by definition.

Figure 4: Perturbation for a set of collinear grid points. Left: Solid dots
indicate $S=\\{s_{1},\ldots,s_{9}\\}$; all other grid points are marked by
empty dots. The binary expansion of the $x$-coordinates of all grid points.
Right: The elements of $S_{1},\ldots,S_{5}$, where $j(1)=0$, $j(2)=1$,
$j(3)=2$, and $j(4)=3$.

We show that ${\rm conv}(\Phi(S))$ has $\mathcal{O}(\log^{2}m)$ vertices in
two steps: First we consider the convex hull of a projection of $\Phi(S)$ to a
plane, and then extend the argument to 3-space.

Convex hull of the orthogonal projection to the $xy$-plane. We consider the
impact of the first step of the perturbation, $\Phi_{1}(S)$. Let
$\Phi^{xy}(S)$ and $\Phi_{1}^{xy}(S)$, resp., be the orthogonal projection of
$\Phi(S)$ and $\Phi_{1}(S)$ to the $xy$-plane.

######  Claim 1.

The convex polygon ${\rm conv}(\Phi^{xy}(S))$ has $\mathcal{O}(\log m)$
vertices.

If a point $\Phi^{xy}(p)$ is a vertex of ${\rm conv}(\Phi^{xy}(S))$, then
$\Phi_{1}^{xy}(p)$ is on the boundary of ${\rm conv}(\Phi_{1}^{xy}(S))$, since
subsequent perturbations are negligible. Note that both $\Phi_{1}^{xy}(s_{1})$
and $\Phi_{1}^{xy}(s_{t})$ are vertices of ${\rm conv}(\Phi_{1}^{xy}(S))$.
These two points decompose the boundary of ${\rm conv}(\Phi_{1}^{xy}(S))$ into
two Jordan arcs: an _upper arc_ and a _lower arc_ in the $xy$-plane. It
suffices to show that each arc contains $\mathcal{O}(\log n)$ points of
$\Phi_{1}^{xy}(S)$. Without loss of generality, consider the upper arc.

######  Claim 2.

Let $s_{\ell}\in S$. If $\Phi_{1}^{xy}(s_{\ell})$ lies in the upper arc of
${\rm conv}(\Phi_{1}^{xy}(S))$, then $s_{\ell}$ is the first or last point in
$S_{a}$ for some $a\in\\{1,\ldots,b\\}$.

We prove the contrapositive of Claim 2. Suppose that $s_{\ell}$ is neither the
first nor the last point in $S_{a}$ for any $a\in\\{1,\ldots,b\\}$. Due to (6)
and $|S_{b}|=1$, there exists an $a\in\\{1,\ldots,b-1\\}$ such that
$s_{\ell}\in S_{a}$ but $s_{\ell}\notin S_{a+1}$. Denote the first and last
points in $S_{a}$ and $S_{a+1}$, resp., by $s_{\sigma(1)},s_{\sigma(2)}$ and
$s_{\tau(1)},s_{\tau(2)}$. Then ${\rm conv}(S_{a})$ and ${\rm conv}(S_{a+1})$,
resp., are the line segments $s_{\sigma(1)}s_{\sigma(2)}$ and
$s_{\tau(1)}s_{\tau(2)}$; see Fig. 5. Note that
$\sigma(1)\leq\tau(1)\leq\tau(2)\leq\sigma(2)$ and $\sigma(1)<\sigma(2)$. Then
we have $\sigma(1)<\ell<\tau(2)$ or $\tau(1)<\ell<\sigma(2)$. Assume w.l.o.g.
that $\sigma(1)<\ell<\tau(2)$.

We show that the point $\Phi_{1}^{xy}(s_{\ell})$ lies below the line segment
$\Phi_{1}^{xy}(s_{\sigma(1)})\Phi_{1}^{xy}(s_{\tau(2)})$, and so it cannot be
on the upper arc of ${\rm conv}(\Phi_{1}^{xy}(S))$. Since the points
$s_{\sigma(1)},s_{\ell},s_{\tau(2)}\in L$ are collinear, and
$\Phi_{1}(p)=p+\varphi_{1,2}(p)$, it is enough to compare the perturbations
incurred by $\varphi_{1,2}$, which depend only on the $x$-coordinates. By the
choice of $a$, we have $s_{\sigma(1)},s_{\ell},s_{\tau(2)}\in S_{a}$. This
means that in the binary expansion of their $x$-coordinates, the last $j(a)$
bits are the same. Regarding the bit $x_{j(a)}(.)$, we know that
$x_{j(a)}(s_{\ell})=0$ and $x_{j(a)}(s_{\tau(2)})=1$. However, $s_{\sigma(1)}$
may or may not be in $S_{a+1}$, and so we do not know
$x_{j(a)}(s_{\sigma(1)})$. Consequently, by using the inequality
$(N)_{\varepsilon}<2\varepsilon$ in (8), we have

$\displaystyle\|\varphi_{1,2}(s_{\sigma(1)})\|$
$\displaystyle\geq\left(\sum_{j=0}^{j(a)-1}x_{j}(s_{\ell})\cdot\varepsilon^{j+1}\right)=:X$
(7) $\displaystyle\|\varphi_{1,2}(s_{\ell})\|$
$\displaystyle<\left(\sum_{j=0}^{j(a)-1}x_{j}(s_{\ell})\cdot\varepsilon^{j+1}\right)+2\varepsilon^{j(a)+2}=X+2\varepsilon^{j(a)+2}$
(8) $\displaystyle\|\varphi_{1,2}(s_{\tau(2)})\|$
$\displaystyle\geq\left(\sum_{j=0}^{j(a)-1}x_{j}(s_{\ell})\cdot\varepsilon^{j+1}\right)+\varepsilon^{j(a)+1}=X+\varepsilon^{j(a)+1}.$
(9)

Since $s_{\sigma(1)}$, $s_{\ell}$, and $s_{\tau(2)}$ are collinear grid
points, we can express $s_{\ell}$ as a convex combination:

$\displaystyle s_{\ell}$ $\displaystyle=\alpha\cdot
s_{\sigma(1)}+(1-\alpha)\cdot s_{\tau(2)}$ (10)

for some coefficient $\frac{1}{n^{1/3}}\leq\alpha\leq 1-\frac{1}{n^{1/3}}$.
Denote by $q$ the point in the line segment
$\Phi_{1}^{xy}(s_{\sigma(1)})\Phi_{1}^{xy}(s_{\tau(2)})$ above $s_{\ell}$.
Then, substituting (7)–(9) into (10), we obtain

$\displaystyle\|q-s_{\ell}\|$
$\displaystyle=\alpha\cdot\|\varphi_{1,2}(s_{\sigma(1)})\|+(1-\alpha)\cdot\|\varphi_{1,2}(s_{\tau(2)})\|$
(11)
$\displaystyle\geq\left(\sum_{j=0}^{j(a)-1}x_{j}(s_{\ell})\cdot\varepsilon^{j+1}\right)+(1-\alpha)\cdot\varepsilon^{j(a)+1}$
$\displaystyle\geq
X+\frac{\varepsilon^{j(a)+1}}{n^{1/3}}>X+2\varepsilon^{j(a)+2}>\|\varphi_{1,2}(s_{\ell})\|,$

if $\varepsilon<\frac{1}{2n^{1/3}}$. This confirms that
$\Phi_{1}^{xy}(s_{\ell})$ lies below the line segment
$\Phi_{1}^{xy}(s_{\sigma(1)})\Phi_{1}^{xy}(s_{\tau(2)})$; and completes the
proof of Claim 2.

Since $b=\mathcal{O}(\log m)$, there are at most $2b=\mathcal{O}(\log m)$
points that are first or last in $S_{1},\ldots,S_{b}$. Consequently, Claim 2
implies that the upper arc of ${\rm conv}(\Phi^{xy}(S))$ has $\mathcal{O}(\log
m)$ vertices. Similarly, one can show that the lower arc of ${\rm
conv}(\Phi^{xy}(S))$ has $\mathcal{O}(\log m)$ vertices (the key difference
for handling the lower arc is that in the recursive definition of the sets
$S_{1}\supset S_{2}\supset\ldots\supset S_{b}$, we would put $S_{a+1}=\\{s\in
S_{a}:x_{j(a)}(s)=0\\}$). Overall, ${\rm conv}(\Phi^{xy}(S))$ has
$\mathcal{O}(\log m)$ vertices; completing the proof of Claim 1.

Figure 5: The points $s_{\ell}$, $s_{\sigma(1)}$, $s_{\sigma(2)}$,
$s_{\tau(2)}$, and $s_{\tau(2)}$; and their perturbations.

Convex hull in 3-space. Consider ${\rm conv}(\Phi(S))$. The orthogonal
projection of ${\rm conv}(\Phi(S))$ to the $xy$-plane is ${\rm
conv}(\Phi^{xy}(S))$. The boundary of ${\rm conv}(\Phi^{xy}(S))$ is the
projection of a closed curve $\gamma$ on the boundary of ${\rm
conv}(\Phi(S))$. We have shown that the projection of $\gamma$, hence $\gamma$
itself, has $\mathcal{O}(\log n)$ vertices. The Jordan curve $\gamma$
partitions the boundary of ${\rm conv}(\Phi(S))$ into two components: An
_upper surface_ and a _lower surface_. It suffices to show that each has
$\mathcal{O}(\log^{2}m)$ vertices.

######  Claim 3.

Let $s_{\ell}\in S$. If $\Phi(s_{\ell})$ is a vertex of the upper surface of
${\rm conv}(\Phi(S))$, then $\Phi^{xy}(s_{\ell})$ is a vertex of ${\rm
conv}(\Phi^{xy}(S_{a}))$ for some $a\in\\{1,2,\ldots,b\\}$.

We prove the contrapositive of Claim 3. Suppose that $s_{\ell}\in S$ but
$\Phi(s_{\ell})$ is not a vertex of ${\rm conv}(\Phi(S_{a}))$ for any
$a\in\\{1,\ldots,b\\}$. Note that (6) implies

${\rm conv}(\Phi^{xy}(S))={\rm conv}(\Phi^{xy}(S_{1}))\supset{\rm
conv}(\Phi^{xy}(S_{2}))\supset\ldots\supset{\rm conv}(\Phi^{xy}(S_{b})).$

There exists some $a\in\\{1,\ldots,b\\}$ such that $s_{\ell}\in S_{a}$ but
$s_{\ell}\notin S_{a+1}$. First triangulate the convex polygon ${\rm
conv}(\Phi^{xy}(S_{a+1}))$; and then triangulate the nonconvex polygon ${\rm
conv}(\Phi^{xy}(S_{a}))\setminus{\rm conv}(\Phi^{xy}(S_{a+1}))$ such that each
triangle is spanned by some vertices of ${\rm conv}(\Phi^{xy}(S_{a}))$ and
some vertices of ${\rm conv}(\Phi^{xy}(S_{a+1}))$. The point
$\Phi^{xy}(s_{\ell})$ lies in some triangle
$\Phi^{xy}(p)\Phi^{xy}(q)\Phi^{xy}(r)$ in which at least one corner is a
vertex of ${\rm conv}(\Phi^{xy}(S_{a+1}))$. Considering the perturbation
$\Phi_{1}(s)=s+\varphi_{1,2}(s)$, the triangle $\Phi(p)\Phi(q)\Phi(r)$ lies
above $\Phi(s_{\ell})$ if $\varepsilon>0$ is sufficiently small, analogously
to (7)–(9) and (10), except that $s_{\ell}$ is now the convex combination of
three grid points $p$, $q$, and $r$. Consequently, $\Phi(s_{\ell})$ cannot be
on the upper surface. This proves Claim 3.

By Claim 2, ${\rm conv}(\Phi^{xy}(S_{a}))$ has $\mathcal{O}(\log m)$ vertices
for all $a\in\\{1,2,\ldots,b\\}$. Summation over all $a=1,\ldots,b$ shows that
there are $\sum_{a=1}^{b}\mathcal{O}(\log m)=\mathcal{O}(\log^{2}m)$ vertices
on the upper surface of ${\rm conv}(\Phi(S)$. Analogously, the lower surface
of ${\rm conv}(\Phi(S))$ also has $\mathcal{O}(\log^{2}m)$ vertices. Overall,
${\rm conv}(\Phi(S))$ has $\mathcal{O}(\log^{2}m)$ vertices. This completes
the proof of Lemma 4.3.

######  Lemma 4.5.

Let $S\subset G$ be a set of coplanar points. Then ${\rm conv}(\Phi(S))$ has
$\mathcal{O}(m^{1/3})$ vertices, where $m=|G\cap{\rm conv}(S)|$.

######  Proof 4.6.

We proceed similarly to the proof of Lemma 4.3. Consider the first coordinate
axis (the $x$\- or the $y$-axis) that is not orthogonal to $F$, and another
coordinate axis that is not parallel to $F$. Assume that $F$ is not orthogonal
to the $x$-axis (or else we would use the $y$-axis); and it is not parallel to
the $y$-axis (or else we would use the $z$-axis). Label the points in $S\cap
F$ as $\\{s_{1},\ldots,s_{t}\\}$ sorted by increasing $x$-coordinates (ties
are broken arbitrarily). Let the binary representation of the $x$-coordinate
of $s\in S$ be $x(s)=\sum_{j=0}^{k-1}x_{j}(s)2^{j}$. We recursively define the
sets

$S_{1}\supset S_{2}\supset\ldots\supset S_{b},$ (12)

for some suitable $b\leq\mathcal{O}(\log m)$ the same way as in the proof of
Lemma 4.3. Let $S_{1}=S$. Given a set $S_{a}\subset S$, for $a\geq 1$, where
the points in $S_{a}$ do not all have the same $x$-coordinates, we define
$S_{a+1}$ as follows. Let $j(a)\geq 1$ be the smallest integer such that
$\\{x_{j(a)}(s):s\in S_{a}\\}=\\{0,1\\}$; and let $S_{a+1}=\\{s\in
S_{a}:x_{j(a)}(s)=1\\}$.

Denote by $M=\mathbb{Z}^{3}\cap F$ the set of grid points in $F$. Based on the
recursion above, we define a sequence of nested sets

$M_{1}\supset M_{2}\supset\ldots\supset M_{b}$ (13)

as follows. Let $M_{1}=M$, and $M_{a+1}=\\{s\in M_{a}:x_{j(a)}(s)=1\\}$ for
$a\in\\{1,\ldots,b-1\\}$. Then $|M_{a}|=\mathcal{O}(m/2^{a})$ for all
$a\in\\{1,\ldots,b\\}$.

Figure 6: The nested sequence $F\supset{\rm
conv}(S_{1})\supset\ldots\supset{\rm conv}(S_{4})$. The point $s_{\ell}$ lies
in ${\rm conv}(S_{2})\setminus{\rm conv}(S_{3})$.

We interpret the above-below relationship with respect to the $y$-axis. Assume
w.l.o.g. that ${\rm conv}(S)$ lies below the face $F$.

######  Claim 4.

Let $s_{\ell}\in S\cap F$. If $\Phi(s_{\ell})$ is a vertex of ${\rm
conv}(\Phi(S\cap F))$, then $s_{\ell}$ lies on the boundary of ${\rm
conv}(S_{a})$ for some $a\in\\{1,\ldots,b\\}$.

We prove the contrapositive of Claim 4. Suppose that $s_{\ell}$ is not on the
boundary of ${\rm conv}(S_{a})$ for any $a\in\\{1,\ldots,b\\}$. Due to (6),
there exists some $a\in\\{1,\ldots,b\\}$ such that $s_{\ell}\in S_{a}$ but
$s_{\ell}\notin S_{a+1}$; see Fig. 6. First triangulate the convex polygon
${\rm conv}(S_{a+1})$; and then triangulate the nonconvex polygon ${\rm
conv}(S_{a})\setminus{\rm conv}(S_{a+1})$ such that each triangle is spanned
by some vertices of ${\rm conv}(S_{a})$ and some vertices of ${\rm
conv}(S_{a+1})$. Then point $s_{\ell}$ lies in some triangle $pqr$, and at
least one corner is a vertex of ${\rm conv}(S_{a+1})$. Considering the
perturbation $\varphi_{1,2}$, the triangle $\Phi(p)\Phi(q)\Phi(r)$ lies above
$\Phi(s_{\ell})$ if $\varepsilon>0$ is sufficiently small. Consequently,
$\Phi(s_{\ell})$ cannot be a vertex of ${\rm conv}(\Phi(S\cap F))$. This
completes the proof of Claim 4.

For every $a\in\\{1,\ldots,b\\}$, the convex hull ${\rm conv}(S_{a}\cap
M_{a})$ has $\mathcal{O}(m_{a}^{1/3})$ vertices and edges, where
$m_{a}=|M_{a}|\leq\mathcal{O}(m/2^{a})$, by Theorem 2.2. Further, by Lemma
2.4, it has $\mathcal{O}((m_{a}/t^{2})^{1/3})$ edges that contain more than
$t$ points in $M_{a}$ for any $t\geq 1$. By Lemma 4.3, if an edge $e$ of ${\rm
conv}(S_{a}\cap M_{a})$ contains more than $t$ grid points, then ${\rm
conv}(\Phi(S\cap e))$ contains $\mathcal{O}(\log^{2}t)$ vertices of $B$. Let
$E_{j}$ be the set of edges $e$ with
$|e\cap\mathbb{Z}^{3}|\in(2^{j-1},2^{j}]$; and
$E=\bigcup_{j\in\mathbb{N}}E_{j}$. Summation over all edges of $S_{a}\cap F$
yields

$\displaystyle\sum_{e\in E}\mathcal{O}(\log^{2}|e\cap\mathbb{Z}^{3}|)$
$\displaystyle=\sum_{j\in\mathbb{N}}|E_{j}|\cdot\mathcal{O}(\log^{2}2^{j})$
$\displaystyle=\sum_{j\in\mathbb{N}}\mathcal{O}\left((m_{a}/2^{2j})^{1/3}\cdot
j^{2}\right)$
$\displaystyle=\mathcal{O}(m_{a}^{1/3})\,\sum_{j\in\mathbb{N}}\frac{j^{2}}{(2^{2/3})^{j}}=\mathcal{O}(m_{a}^{1/3}).$

Finally, summation for all $a\in\\{1,\ldots,b\\}$ yields

$\sum_{a=1}^{b}\mathcal{O}(m_{a}^{1/3})=\sum_{a=1}^{b}\mathcal{O}\left((m/2^{a})^{1/3}\right)=\mathcal{O}\left(m^{1/3}\,\sum_{a\geq
1}2^{-a/3}\right)=\mathcal{O}(m^{1/3}),$

as claimed.

######  Lemma 4.7.

Let $S\subset G$ and $P={\rm conv}(S)$. Suppose that $P$ has $f$ faces (of any
dimension), which contain $m_{1},\ldots,m_{f}$ lattice points in their
interior. Then $\sum_{i=1}^{f}m_{i}^{1/3}=\mathcal{O}(n^{1/2})$.

######  Proof 4.8.

The surface area of the lattice polytope $P={\rm conv}(S)$ is bounded above by
that of the cube ${\rm conv}(G)$, which is $6n^{2/3}$. Let $\mathcal{F}$ be
the set of all facets of $P$. Then summation of the area over all facets
yields an upper bound $\sum_{F\in\mathcal{F}}\mathcal{O}({\rm
Area}(F))=\mathcal{O}(n^{2/3})$.

For every face $F\in\mathcal{F}$, let $\mathbf{n}_{F}=(a,b,c)$ be the integer
normal vector of the plane spanned by $F$, where $a,b,c\in\mathbb{Z}$, and
$\mathrm{gcd}(a,b,c)=1$. It is known that $F$ contains $\mathcal{O}({\rm
Area}(F)/\|\mathbf{n}\|_{2})$ lattice points [5].

For every integer $j\in\mathbb{N}$, let $\mathcal{F}_{j}$ be the set of facets
$F\in\mathcal{F}$ such that $\|\mathbf{n}_{F}\|_{2}\in(2^{j-1},2^{j}]$. In
particular, a face $F\in\mathcal{F}_{j}$ contains $\mathcal{O}({\rm
Area}(F)/2^{j})$ lattice points. For an integer $N\in\mathbb{N}$, let
$r_{3}(N)$ denote the number of representations of $N$ as a sum of squares of
three integers (where signs and the order of terms matters). It is known [24,
Theorem 340] that

$\sum_{N=1}^{M}r_{3}(N)=\frac{4}{3}\pi M^{3/2}+\mathcal{O}(M).$

In particular, for $M=2^{2j}$, we have
$\sum_{N=1}^{M}r_{3}(N)=\Theta(2^{3j})$, and so
$|\mathcal{F}_{j}|=\mathcal{O}(2^{3j})$.

The total area of all facets in $\mathcal{F}_{j}$ is $\mathcal{O}(n^{2/3})$
for each $j\in\mathbb{N}$. Thus the facets in $\mathcal{F}_{j}$ contain at
most $\sum_{F\in\mathcal{F}_{j}}\mathcal{O}({\rm
Area}(F)/2^{j})=\mathcal{O}(n^{2/3}/2^{j})$ lattice points. Jensen’s
inequality gives

$\displaystyle\sum_{F\in\mathcal{F}_{j}}m_{i}^{1/3}\log m_{i}$
$\displaystyle\leq|\mathcal{F}_{j}|\cdot\left(\frac{n^{2/3}/2^{j}}{|\mathcal{F}_{j}|}\right)^{1/3}$
$\displaystyle=|\mathcal{F}_{j}|^{2/3}n^{2/9}2^{-j/3}=\mathcal{O}(n^{2/9}2^{(2/3)3j-j/3})=\mathcal{O}(n^{2/9}2^{5j/3}).$
(14)

Since the number of facets is $\mathcal{O}(n^{1/2})$, then
$|\mathcal{F}_{j}|=\mathcal{O}(n^{1/2})$ for all $j\in\mathbb{N}$; and (4.8)
becomes:

$\displaystyle\sum_{F\in\mathcal{F}_{j}}m_{i}^{1/3}$
$\displaystyle\leq|\mathcal{F}_{j}|\cdot\left(\frac{n^{2/3}/2^{j}}{|\mathcal{F}_{j}|}\right)^{1/3}$
$\displaystyle\leq|\mathcal{F}_{j}|^{2/3}n^{2/9}2^{-j/3}=\big{(}\mathcal{O}(n^{1/2})\big{)}^{2/3}n^{2/9}2^{-j/3}=\mathcal{O}(n^{5/9}2^{-j/3}).$
(15)

The bounds in (4.8) and (4.8) are equal, up to constant factors, when
$2^{j}=n^{1/6}$, or equivalently, $j=\frac{1}{6}\log n$. Summation over all
$j\in\mathbb{N}$ yields

$\displaystyle\sum_{i=1}^{f}m_{i}^{1/3}$
$\displaystyle=\sum_{j\in\mathbb{N}}\sum_{F\in\mathcal{F}_{j}}m_{i}^{1/3}$
$\displaystyle=\sum_{j=1}^{\log
n^{1/6}}\sum_{F\in\mathcal{F}_{j}}m_{i}^{1/3}+\sum_{j>\log
n^{1/6}}\sum_{F\in\mathcal{F}_{j}}m_{i}^{1/3}$
$\displaystyle\leq\sum_{j=1}^{\log
n^{1/6}}\mathcal{O}(n^{2/9}2^{5j/3})+\sum_{j>\log
n^{1/6}}\mathcal{O}(n^{5/9}/2^{j/3})$
$\displaystyle=\mathcal{O}(n^{2/9+5/18})+\mathcal{O}(n^{5/9-1/18})=\mathcal{O}(n^{1/2}).$

We can now complete the proof of Theorem 1.6. Recall that
$G=\\{0,\ldots,2^{k}-1\\}^{3}$ is a section of the integer lattice
$\mathbb{Z}^{3}$ with $n=2^{3k}$ points. We have $A=\Phi(G)$; and $C\subset G$
such that $B=\Phi(C)$ is in convex position. As noted above, every point in
$C$ lies on the boundary of the lattice polytope $P={\rm conv}(C)$.

If a facet $F$ of $P$ contains $m$ lattice points, then $F$ contains
$\mathcal{O}(m^{1/3})$ points of $C$ by Lemma 4.5. Summation over all facets
yields $\mathcal{O}(n^{1/2})$ by Lemma 4.7. Consequently, we have
$|B|=|C|=\mathcal{O}(n^{1/2})$, as required.

##  5 Approximation algorithm: Proof of Theorem 1.7

In this section we analyze the randomized algorithm described in Section 3 and
show that its approximation factor is $\Omega(n^{-1/6})$. We also make some
small twists that allow for an efficient implementation. We are given an
$n$-element set $A\subset\mathbb{R}^{3}$ with
$\Delta(A)\leq\mathcal{O}(n^{1/3})$ As in the proof of Theorem 1.4, we may
assume that $A\subset B$, where $B$ is a ball of radius
$R\leq\mathcal{O}(n^{1/3})$ centered at $O$; e.g., a smallest enclosing ball
of $A$. First, deterministically construct a (single) spherical packing
$\mathcal{P}$ on a sphere $C$ congruent to $B$ of prescribed minimum size
$\Theta(n^{1/2})$; ($\mathcal{P}$ does not have to be maximal). For example,
slice the sphere by latitudes, and choose equally spaced spherical caps
between consecutive latitudes. Second, the randomized phase proceeds as
follows. Guess a center for a ball $C$ and apply a random rotation in $SO(3)$
(applying the same rotation to all caps in $\mathcal{P}$), and then test
whether a constant fraction of the caps are nonempty; if not, repeat the
process. The expected number of repetitions is bounded by a constant (the sum
of a geometric series).

Approximation ratio. As in the proof of Theorem 1.4, we may assume that
$A\subset B$, where $B$ is a ball of radius $R=\alpha n^{1/3}$ centered at
$O$. Let $A_{\textsf{OPT}}\subset A$ be a maximum-size subset in convex
position, i.e., $\textsf{OPT}=|A_{\textsf{OPT}}|$. Since
$A_{\textsf{OPT}}\subset B$, we have

${\rm Area}(\partial({\rm conv}(A_{\textsf{OPT}})))\leq{\rm Area}(\partial
B)=4\pi R^{2}=\mathcal{O}(n^{2/3}).$

Since $A$ is density-restricted, then $\textsf{OPT}=\mathcal{O}(n^{2/3})$.
(The above argument is the $3$-dimensional variant of [4, Theorem 3.2].) On
the other hand, Theorem 1.4 yields . Consequently, the approximation ratio is

$\frac{\alg}{\textsf{OPT}}=\Omega\left(\frac{n^{1/2}}{n^{2/3}}\right)=\Omega(n^{-1/6}),$

as claimed.

Running time analysis. A smallest enclosing ball of $n$ points in
$\mathbb{R}^{3}$ can be computed in $\mathcal{O}(n)$ expected time [38], and a
random rotation and translation in $\mathcal{O}(1)$ time [34]. The packing
$\mathcal{P}$ can be constructed in $\mathcal{O}(n^{1/2})$ time (i.e., in time
linear in $|\mathcal{P}|$). We next consider the time complexity of
$\Theta(n^{1/2})$ range-emptiness queries for spherical cap ranges. After
$\mathcal{O}(n)$ preprocessing, points outside the chosen ball are excluded
from further consideration. Then each range-emptiness query for a spherical
cap is equivalent to (and answered by) a _halfspace emptiness query_
determined by the plane containing the base of the cap. (Here we take
advantage of the fact that all spherical cap ranges pertain to the same ball.)
After $\mathcal{O}(n\log{n})$ expected preprocessing time, such queries in
$3$-space can be answered in $\mathcal{O}(\log{n})$ time per query using the
algorithm by Afshani and Chan [1]; but also by other algorithms, see [2, 3].
Consequently, the range-emptiness queries can be answered in
$\mathcal{O}(n^{1/2}\log{n})$ time. Adding up the running times of the steps
we have
$\mathcal{O}(n^{1/2})+\mathcal{O}(n)+\mathcal{O}(n\log{n})+\mathcal{O}(n^{1/2}\log{n})=\mathcal{O}(n\log{n})$.
Overall, the randomized algorithm runs in $\mathcal{O}(n\log{n})$ expected
time. ∎

### Generalization to higher dimensions.

The machinery developed here generalizes to $\mathbb{R}^{d}$.

######  Theorem 5.1.

Given any $n$-element point set in $\mathbb{R}^{d}$ in general position,
satisfying $\Delta(A)\leq\alpha n^{1/d}$ for a fixed $\alpha$, a
$\Omega\left(n^{-\frac{(d-1)}{d(d+1)}}\right)$-factor approximation of the
maximum size convex subset of points can be computed by a randomized algorithm
in $\mathcal{O}(n\log{n})$ expected time.

The proof of Theorem 5.1 is analogous to the proof of Theorem 1.7. The
approximation ratio is

$\frac{\alg}{\textsf{OPT}}=\Omega\left(\frac{n^{(d-1)/(d+1)}}{n^{(d-1)/d}}\right)=\Omega\left(n^{-\frac{(d-1)}{d(d+1)}}\right).$

As the exponent tends to zero when $d\to\infty$, the approximation ratio
improves with the dimension (if $n$ is sufficiently large). As such, our
algorithm enjoys the ‘blessing of dimensionality’ rather than the usual ‘curse
of dimensionality’.

##  6 Concluding remarks

Conlon and Lim [17] raised the question of whether the extension of the Valtr
grid to higher dimensions presented in their paper bears any influence on the
problem of constructing density-restricted sets with no large convex subsets
in higher dimensions. Here we gave a positive answer and a tight asymptotic
bound for $d=3$. We also obtained the first approximation algorithm for the
problem of finding a maximum-size subset of points in convex position in a
density-restricted set in $\mathbb{R}^{3}$. Next, we list a few open questions
regarding the remaining gaps and the quality of approximation.

  1. 1.

Is the problem of finding a maximum-cardinality subset in convex position, in
given finite set in $\mathbb{R}^{3}$, still NP-complete for density-restricted
sets?

  2. 2.

Is there a constant-ratio approximation algorithm for finding a maximum-size
subset in convex position for a given finite set in $\mathbb{R}^{3}$? Is there
one for density-restricted sets?

Next are several open questions regarding the size of the largest convex
subset in point sets where the density constraints are relaxed. Let $A$ be a
set of $n$ points in general position in $\mathbb{R}^{d}$ satisfying
$\Delta(A)\leq\alpha n^{\tau}$, where $d\geq 2$ and $\alpha,\tau>0$ are
constants. Note that for $\tau\geq 1$, only poly-logarithmic bounds are in
effect [26].

  1. 3.

Let $d=2$. What upper bounds on the size of the largest convex subset can be
derived when $\tau\in\left(\frac{1}{2},1\right)$? What lower bounds can be
derived when $\tau\in\left[\frac{3}{4},1\right)$?

  2. 4.

Let $d=3$. What upper bounds on the size of the largest convex subset can be
derived when $\tau\in\left(\frac{1}{3},1\right)$? What lower bounds can be
derived when $\tau\in\left[\frac{2}{3},1\right)$?

A natural candidate for a lower bound in the third question is a suitable
perturbation—in the form of the Valtr grid—of a rectangular section of the
integer lattice. Indeed, if $A$ is a $n^{\tau}\times n^{1-\tau}$ section of
this lattice and $\tau>1/2$, then $\Delta(A)=\mathcal{O}(n^{\tau})$.

We conclude with the following conjecture that generalizes Lemma 2.4:

######  Conjecture 6.1.

For every finite set $S\subset\mathbb{Z}^{d}$, $d\geq 2$, and for every
integer $t$, $1\leq t\leq V^{1/d}$, the lattice polytope ${\rm conv}(S)$ has
$\mathcal{O}\left(\left(V/t^{d}\right)^{\frac{d-1}{d+1}}\right)$ faces (of any
dimension) that contain more than $t$ points in $\mathbb{Z}^{d}$, where
$V={\rm Vol}({\rm conv}(S))>0$.

Using this technical tool, our upper bound
$\gamma_{3}(n)=\mathcal{O}(n^{1/2})$ in Section 4 would generalize to higher
dimensions. Together with the direct generalization of our lower bound
$\gamma_{3}(n)=\Omega(n^{1/2})$ in Section 3, it would yield an alternative
proof of the bound $\gamma_{d}(n)=\Theta_{d}\left(n^{\frac{d-1}{d+1}}\right)$
for $d\geq 4$, obtained by Bukh and Dong [14] independently.

## References

  * [1] Peyman Afshani and Timothy M. Chan, Optimal halfspace range reporting in three dimensions, _Proc. 20th ACM-SIAM Symposium on Discrete Algorithms_ , 2009, pp. 180–186.
  * [2] Pankaj K. Agarwal, Range searching, Chap. 40 in _Handbook of Discrete and Computational Geometry_ (Jacob E. Goodman, Joseph O’Rourke, and Csaba D. Tóth, eds.), 3rd edition, CRC Press, Boca Raton, 2017, pp.1057–1092.
  * [3] Pankaj K. Agarwal, Simplex range searching and its variants: a review, in _A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek_ (Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, editors), Springer, Cham, 2017, pp. 1–30.
  * [4] Noga Alon, Meir Katchalski, and William R. Pulleyblank, The maximum size of a convex polygon in a restricted set of points in the plane, Discrete & Computational Geometry 4 (1989), 245–251.
  * [5] George E. Andrews, An asymptotic expression for the number of solutions of a general class of Diophantine equations, _Transactions of the American Mathematical Society_ 99(2) (1961), 272–277.
  * [6] George E. Andrews, A lower bound for the volume of strictly convex bodies with many boundary lattice points, _Transactions of the American Mathematical Society_ 106(2) (1963), 270–279.
  * [7] Imre Bárány, Extremal problems for convex lattice polytopes: A survey, in _Surveys on Discrete and Computational Geometry: Twenty Years Later_ (Jacob E. Goodman, János Pach and Richard Pollack, editors), vol. 453 of _Contemporary Mathematics_ , ACM, 2008, pp. 87–103.
  * [8] Imre Bárány and David Larman, The convex hull of the integer points in a large ball, _Math Ann_ 312, (1998), 167–181.
  * [9] Imre Bárány and János Pach, On the number of convex lattice polygons, _Combinatorics, Probability & Computing_ 1 (1992), 295–302.
  * [10] Imre Bárány and Anatoly M. Vershik, On the number of convex lattice polytopes, _Geometric and Functional Analysis_ 2 (1992), 381–393.
  * [11] Luis Barba, Frank Duque, Ruy Fabila-Monroy, and Carlos Hidalgo-Toscano, Drawing the Horton set in an integer grid of minimum size, _Comput. Geom._ 63 (2017), 10–19.
  * [12] Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor, On metric Ramsey-type phenomena, _Ann. Math._ 162(2) (2005), 643–709.
  * [13] Peter Braß, William Moser, and János Pach, _Research Problems in Discrete Geometry_ , Springer, New York, 2005.
  * [14] Boris Bukh and Zichao Dong, Convex polytopes in restricted point sets in $\mathbb{R}^{d}$, manuscript, 2022, preprint available at arXiv.org/abs/2204.02487v2.
  * [15] Jean-Lou de Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot, Convex polygons in Cartesian products, _Journal of Computational Geometry_ 11(2) (2020), 205–233.
  * [16] Vašek Chvátal and Gheza T. Klincsek, Finding largest convex subsets, _Congressus Numerantium_ , 29 (1980), 453–460.
  * [17] David Conlon and Jeck Lim, Fixing a hole, manuscript, 2021, preprint available at arXiv.org/abs/2108.07087.
  * [18] Frank Duque, Ruy Fabila-Monroy, and Carlos Hidalgo-Toscano, Point sets with small integer coordinates and no large convex polygons, Discrete & Computational Geometry 59(2) (2018), 461–476.
  * [19] Herbert Edelsbrunner, Pavel Valtr, and Emo Welzl, Cutting dense point sets in half, Discrete & Computational Geometry 17(3) (1997), 243–255.
  * [20] Paul Erdős and György Szekeres, A combinatorial problem in geometry, _Compositio Mathematica_ 2 (1935), 463–470.
  * [21] Paul Erdős and György Szekeres, On some extremum problems in elementary geometry, _Annales Universitatis Scientiarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica_ 3-4 (1960), 53–62.
  * [22] Tobias Gerken, Empty convex hexagons in planar point sets, _Discrete & Computational Geometry_ 39(1-3) (2008), 239–272.
  * [23] Panos Giannopoulos, Christian Knauer, and Daniel Werner, On the computational complexity of Erdős-Szekeres and related problems in $\mathbb{R}^{3}$, _Proc. 21st European Symposium on Algorithms_ , vol. 8125 of LNCS (2013), pp. 541–552.
  * [24] Godfrey H. Hardy and Edward M. Wright, _An Introduction to the Theory of Numbers_ , 5th edition, Oxford University Press, 1979.
  * [25] Joseph D. Horton, Sets with no empty convex 7-gons, _Canadian Mathematical Bulletin_ 26(4) (1983), 482–484.
  * [26] Gyula Károlyi and Pavel Valtr, Configurations in $d$-space without large subsets in convex position, _Discrete & Computational Geometry_ 30(2) (2003), 277–286.
  * [27] Sergei V. Konyagin and S. V. Sevastyanov, Estimation of the number of vertices of a convex integral polyhedron in terms of its volume, _Funk. Anal. Pril._ 18 (1984), 13–15 (in Russian). English translation: _Funct. Anal. Appl._ 18 (1984), 11–13.
  * [28] István Kovács and Géza Tóth, Dense point sets with many halving lines, _Discrete & Computational Geometry_ 64(3) (2020), 965–984.
  * [29] Jiří Matoušek, _Lectures on Discrete Geometry_ , Springer, New York, 2002.
  * [30] Roger E. Miles, On random rotations in $\mathbb{R}^{3}$, _Biometrika_ 52 (1965), 636–639.
  * [31] Walter D. Morris and Valeriu Soltan, The Erdős–Szekeres problem, in _Open Problems in Mathematics_ , John Nash and Michael Rassias (editors), Springer, 2016, pp. 351–375.
  * [32] Carlos M. Nicolás, The empty hexagon theorem, _Discrete & Computational Geometry_ 38(2) (2007), 389–397.
  * [33] Wolfgang M. Schmidt, Integer points on curves and surfaces, _Monatshefte für Mathematik_ 99 (1985), 45–72.
  * [34] Ken Shoemake, Uniform random rotations, in _Graphics Gems III_ (David Kirk, editor), Morgan Kaufmann, San Franciscio, CA, 1992, pp. 124–132.
  * [35] Andrew Suk, On the Erdős-Szekeres convex polygon problem, _Journal of the American Mathematical Society_ 30 (2017), 1047–1053.
  * [36] Pavel Valtr, Convex independent sets and 7-holes in restricted planar point sets, _Discrete & Computational Geometry_ 7(2) (1992), 135–152.
  * [37] Pavel Valtr, _Planar point sets with bounded ratios of distances_ , PhD Thesis, Freie Universität Berlin (1994).
  * [38] Emo Welzl, Smallest enclosing disks (balls and ellipsoids), in _New Results and New Trends in Computer Science_ (Hermann Maurer, ed.) vol. 555 of LNCS, Springer, Heidelberg, 1991, pp. 359–370.
  * [39] David P. Williamson and David B. Shmoys, _The Design of Approximation Algorithms_ , Cambridge University Press, 2011.