Time complexity of d-dimensional convex hull 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?
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