CODEWITHSUNDEEP
matlabconvex-hullnumerical-computingqhull
Alef
Alef

Reputation: 51

QuickHull worst case

QHull (and perhaps other good implementations of QuickHull) works really well and fast in many cases. However, we know theoretically that its worst case can be O(n^2). In practice I have not seen any numerical example with many dimensions (i.e., 20 or 100) where QHull works poorly.

Do you know of a numerical example where QHull works poorly, or gives the wrong result, or whatever that shows it cannot be applied here.

Upvotes: 2

Views: 686

Answers (1)

Daniel
Daniel

Reputation: 36710

For multidimensional cases you have to generalize what A. Donda said: Generate a set of Points P with norm(p)==1 for each Point p in P. The convex hull is P (unless two points are identical) and will result in a bad running time of ~O(n^2)

For the 2D Case this will choose points on a circle, for 3D points on a sphere.

Upvotes: 3

Related Questions