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?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityConsider 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