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?
2
$\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
8
$\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
