Return to Answer

Under the assumption, that $n$ points in random order are given, the best algorithm seems to be to construct the generalization of the Delaunay Triangulation to $d$-dimensional Euclidean space; that yields a collection of empty hyper-balls that are defined via $d+1$ of the points; the number of those hyper-balls is $O(n^{\lceil d/2 \rceil})$.
The bound on the number of empty hyper-balls proves that the convex hull of $n$ points can't have an exponential number of faces like e.g. $O(2^n)$.

From that collection of hyperballs the ones, whose center is outside the convex hull of their defining $k>=d+1$ points, are not inside the convex hull of the $n$ points and are not considered further.

Then one has to check, whether the radius of any of the remaining hyper-balls is at least $1$.

From the efficient construction of the Delaunay Triangulation in higher dimensions, it follows, that the answer to the question is yes.

The situation doesn't change, if only the points on the convex hull shall be taken into account; this is so, because the points on the convex hull can also be efficiently determined via a generalized gift-wrapping algorithm and then the generalized Delaunay Triangulation can be constructed for those points and finally the largest empty hyper-ball can be determined as described before.

Under the assumption, that $n$ points in random order are given, the best algorithm seems to be to construct the generalization of the Delaunay Triangulation to $d$-dimensional Euclidean space; that yields a collection of empty hyper-balls that are defined via $d+1$ of the points; the number of those hyper-balls is $O(n^{\lceil d/2 \rceil})$.
The bound on the number of empty hyper-balls proves that the convex hull of $n$ points can't have an exponential number of faces like e.g. $O(2^n)$.

From that collection of hyperballs the ones, whose center is outside the convex hull of their defining $k>=d+1$ points, are not inside the convex hull of the $n$ points and are not considered further.

Then one has to check, whether the radius of any of the remaining hyper-balls is at least $1$.

From the efficient construction of the Delaunay Triangulation in higher dimensions, it follows, that the answer to the question is yes.

The situation doesn't change, if only the points on the convex hull shall be taken into account; this is so, because the points on the convex hull can also be efficiently determined via a generalized gift-wrapping algorithm and then the generalized Delaunay Triangulation can be constructed for those points and finally the largest empty hyper-ball can be determined as described before.

If the unit ball is centered at the origin, then one has to check, whether distance of the the faces of the convex hull that were reported by the gift-wrapping algorithm, is not less than $1$.

Under the assumption, that $n$ points in random order are given, the best algorithm seems to be to construct the generalization of the Delaunay Triangulation to $d$-dimensional Euclidean space; that yields a collection of empty hyper-balls that are defined via $d+1$ of the points; the number of those hyper-balls is $O(n^{\lceil d/2 \rceil})$.
The bound on the number of empty hyper-balls proves that the convex hull of $n$ points can't have an exponential number of faces like e.g. $O(2^n)$.

From that collection of hyperballs the ones, whose center is outside the convex hull of their defining $k>=d+1$ points, are not inside the convex hull of the $n$ points and are not considered further.

Then one has to check, whether the radius of any of the remaining hyper-balls is at least $1$.

From the efficient construction of the Delaunay Triangulation in higher dimensions, it follows, that the answer to the question is yes.

Under the assumption, that $n$ points in random order are given, the best algorithm seems to be to construct the generalization of the Delaunay Triangulation to $d$-dimensional Euclidean space; that yields a collection of empty hyper-balls that are defined via $d+1$ of the points; the number of those hyper-balls is $O(n^{\lceil d/2 \rceil})$.
The bound on the number of empty hyper-balls proves that the convex hull of $n$ points can't have an exponential number of faces like e.g. $O(2^n)$.

From that collection of hyperballs the ones, whose center is outside the convex hull of their defining $k>=d+1$ points, are not inside the convex hull of the $n$ points and are not considered further.

Then one has to check, whether the radius of any of the remaining hyper-balls is at least $1$.

From the efficient construction of the Delaunay Triangulation in higher dimensions, it follows, that the answer to the question is yes.

The situation doesn't change, if only the points on the convex hull shall be taken into account; this is so, because the points on the convex hull can also be efficiently determined via a generalized gift-wrapping algorithm and then the generalized Delaunay Triangulation can be constructed for those points and finally the largest empty hyper-ball can be determined as described before.

The best algorithm seems to be to construct the generalization of the Delaunay Triangulation to $d$-dimensional Euclidean space; that yields a collection of empty hyper-balls that are defined via $d+1$ of the points.

From that collection of hyperballs the ones, whose center is outside the convex hull of their defining $k>=d+1$ points, are not inside the convex hull of the $n$ points and are not considered further.

Then one has to check, whether the radius of any of the remaining hyper-balls is at least $1$.

From the efficient construction of the Delaunay Triangulation in higher dimensions, it follows, that the answer to the question is yes.

Under the assumption, that $n$ points in random order are given, the best algorithm seems to be to construct the generalization of the Delaunay Triangulation to $d$-dimensional Euclidean space; that yields a collection of empty hyper-balls that are defined via $d+1$ of the points; the number of those hyper-balls is $O(n^{\lceil d/2 \rceil})$.
The bound on the number of empty hyper-balls proves that the convex hull of $n$ points can't have an exponential number of faces like e.g. $O(2^n)$.

From that collection of hyperballs the ones, whose center is outside the convex hull of their defining $k>=d+1$ points, are not inside the convex hull of the $n$ points and are not considered further.

Then one has to check, whether the radius of any of the remaining hyper-balls is at least $1$.

From the efficient construction of the Delaunay Triangulation in higher dimensions, it follows, that the answer to the question is yes.