14
$\begingroup$

Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time? The convex hull itself might have an exponential number of facets so we cannot afford explicitly to compute it.

My main interest is not in computer precision so we can make whatever assumptions help avoid that in relation to the points themselves (for example they only have integer coordinates).

$\endgroup$
6
  • $\begingroup$ Polynomial time in what? Are you fixing $d$ and varying $n,$ or are you varying both? $\endgroup$
    – Igor Rivin
    Sep 10, 2013 at 16:38
  • $\begingroup$ @IgorRivin I should have said. Polynomial in both $n$ and $d$. You can, for example, determine if an arbitrary fixed point is in the convex hull in polynomial time by a reasonably straightforward application of linear programming. $\endgroup$
    – Simd
    Sep 10, 2013 at 16:45
  • $\begingroup$ how is the set of points given? They could be either in random order or, be sorted in some way (e.g. lexicographical). Further, you should define what is meant by "the unit ball": is it centered at the origin or did you mean "a unit ball", which could be centered anywhere? $\endgroup$ Sep 11, 2013 at 5:26
  • $\begingroup$ In your answer to Igor Rivin you mentioned linear programming for checking whether a point is inside the convex hull; in linear programming the points of the convex hull are not explicitly given, but rather implicitly via the intersection of half-spaces. Maybe you should rethink, how your convex hull is given, via points or via the intersection of half-spaces. In the latter case the problem can be solved efficiently via linear programming $\endgroup$ Sep 11, 2013 at 5:49
  • $\begingroup$ Yet another question: are the $n$ points in convex configuration or can some of the points be inside the convex hull? Is it assumed that the convex hull is $d$-dimensional? $\endgroup$ Sep 11, 2013 at 6:13

2 Answers 2

14
$\begingroup$

The problem is NP hard. Here is a proof sketch.

The problem is to determine if there is a point $y$ with $\|y\|=1$ outside of the convex hull of given points $x_1,\dots, x_n$. Note that such point exists if and only if there is hyperplane at distance less than $1$ from the origin such that all points $x_1, \dots, x_n$ and $0$ lie on one side of the hyperplane (consider a hyperplane $\pi$ separating $x_1,\dots, x_n, 0$ and $y$).

So the problem can be stated as follows: is there $a\in {\mathbb R}^d$ s.t.

  1. $\langle a, x_i\rangle \leq 1$ (that is, all $x_i$ lie in the half-space $\{x: \langle a, x\rangle\leq 1\}$);
  2. $\|a\| > 1$.

Note that this problem is equivalent to the following well-known problem:

We are given a convex polytope $\cal P$, a positive definite matrix $A$ and a number $t$, find $x\in \cal P$ such that $x^T A x > t$. ($\cal P$ is described by a system of linear equations).

The optimization version of this problem is:

Quadratic Programming (Non-convex Linearly Constrained Quadratic Programming with Positive Definite Matrix). We are given a convex polytope $\cal P$ and and a positive definite matrix $A$, find $x\in \cal P$ that maximizes $x^T A x$.

This problem is known to be NP hard.

It is even NP-hard to optimize $x^T A x$ when $\cal P$ is the unit cube $\{(b_1, \dots, b_d): -1\leq b_i \leq 1\}$ (this problem is known as Integer Quadratic Programming with Positive Definite Matrix). In particular, the MAX CUT problem is a special case of this problem. Let $G$ be a graph on $n$ vertices and $L$ be its Laplacian. Then $\max_{x\in\{\pm 1\}^n} x^T L x$ is equal to the size of the maximum cut in $G$ ($L$ is positive semi-definite, not positive definite, but this difference is not important; e.g. we can consider $L'=L+\varepsilon I$ with very small $\varepsilon$). The NP-hardness of MAX CUT was proved by Karp in

Richard M. Karp (1972). Reducibility Among Combinatorial Problems. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.

$\endgroup$
2
  • $\begingroup$ Thank you. Does this well-known problem have a standard name so I can look it and its NP-hardness proof up? $\endgroup$
    – Simd
    Sep 12, 2013 at 10:17
  • $\begingroup$ I added some references. $\endgroup$
    – Yury
    Sep 12, 2013 at 12:10
2
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Thank you. I consider $n^{\lceil d/2 \rceil}$ to be exponential in $d$ however. My question is whether there is an algorithm that is polynomial in both $n$ and $d$. $\endgroup$
    – Simd
    Sep 11, 2013 at 9:56
  • $\begingroup$ @octonots as the construction of the convex hull is exponential in $d$, the answer to your question is no, because if the unit sphere is inside the convex hull, it can come arbitrarily close to a face, while the distance to the vertices may stay above some fixed value; so one has to construct the hyperplanes through the faces of the convex hull in order to calculate their distance from the origin. $\endgroup$ Sep 11, 2013 at 10:08
  • $\begingroup$ I suppose an interesting subquestion is whether it is even in NP. However I am not sure one can rule out a polynomial time algorithm so easily. $\endgroup$
    – Simd
    Sep 11, 2013 at 10:44
  • $\begingroup$ A first step to prove that it could be polynomial, would be to prove that it is not necessary to check $O(n^{\lceil d/2 \rceil})$ faces of the convex hull; I doubt that that is possible. Suppose you have a convex hull that contains the unit ball; intersect that with a halfspace that contains the origin and intersects the unit ball hoping to be able to detect efficiently from the resulting set of points the ones that define the hyperplane that cuts the unit-ball is very optimistic. $\endgroup$ Sep 11, 2013 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.