Skip to main content
2 of 4
typos and added tags
A.Schulz
  • 12.3k
  • 1
  • 42
  • 64

Lower bound for Convex hull

By making use of the fact that sorting $n$ numbers requires $(n \log n)$ steps for any optimal algorithm (which uses 'comparison' for sorting), how can I prove that finding the convex-hull of $n$ points has the lower bound of $\Omega (n \log n)$ steps?

pnp
  • 763
  • 1
  • 7
  • 17