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?

  • 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. – Kaveh Aug 18 '14 at 22:12
up vote 8 down vote accepted

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.