I'm trying to find an efficient (polynomial time) algorithm that will be able to construct a convex hull out of n-points in d-dimensions. Most algorithms are only suitable for 2 or 3-dimensions (like Graham Scan or Jarvis March). I also looked through https://www.cs.princeton.edu/~chazelle/pubs/ConvexHullAlgorithm.pdf which seems to apply to many dimensions, but its time complexity is suboptimal. Can anyone suggest a better algorithm to use in this case, or does one simply not exist?

  • 2
    $\begingroup$ The widely used Quickhull algorithm was published in 1996 after the paper you've mentioned. I don't know what the current best asymptotic complexity is or where to find a good implementation. $\endgroup$ – Brian Borchers Dec 1 '17 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.