Consider the convex hull problem in $\Re^d$:
Input: a list of $n$ points $S$ in $\Re^d$,
Output: the vertices of the convex hull of $S$.
What is the best lower bound on the time complexity of the $d$-dimensional convex hull problem?
$\begingroup$
$\endgroup$
-
$\begingroup$ Lower bounds are dependent on computational models one works in not just problems, you should specify in the question the model(s) you are interested in if you have any specific one in mind. $\endgroup$ – Kaveh Aug 18 '14 at 22:12
$\begingroup$
$\endgroup$
I don't know any nontrivial lower bounds other than the $\Omega(n\log n)$ algebraic-decision-tree lower bound for two dimensions, which also extends to larger $d$.
As for upper bounds: In 3d, the whole hull can be found in $O(n\log n)$; in four or higher dimensions that doesn't work because the hull complexity grows exponentially with $d$, but nevertheless for any fixed $d$, finding all vertices can be done in time $O(n^2)$ (determining whether a given point is a vertex can be done in linear time by solving a linear program), and the Chan reference below improves this slightly.
See
Ottmann and Scheurer, "Enumerating extreme points in higher dimensions", STACS 1995 and Nordic J. Comput. 2001
Chan, "Output-sensitive results on convex hulls, extreme points, and related problems", DCG 1996
Helbling, "Extreme points in medium and high dimensions", ETH thesis 2010
answered Aug 17 '14 at 0:59
-
$\begingroup$ Doesn't the LP approach show that one can enumerate all the convex hull vertices in fixed polynomial time in any dimension? $\endgroup$ – Chandra Chekuri Mar 10 at 13:59
-
$\begingroup$ I assume you saw the "for all fixed $d$" part of my answer and that what you mean is that LP gives polynomial time even when $d$ is variable. Maybe, but variable-dimension LP takes time polynomial in (#vars,#constraints,numerical precision of input coordinates) and because of the numerical precision part isn't strongly polynomial. The fixed-dimension results, on the other hand, are strongly polynomial for constant $d$, but with a non-polynomial dependence on $d$. $\endgroup$ – David Eppstein Mar 10 at 23:32
-
$\begingroup$ Yes, that is what I meant. I thought it would be useful to point out the general case even though the LP algorithm is not strongly polynomial. Also the point about hull coplexity growing exponentially with d is somewhat misleading because that is not necessarily relevant here. For instance LP may have a strongly poly time algorithm. $\endgroup$ – Chandra Chekuri Mar 12 at 0:25
