computing convex hull by quick hull algorithm

0
votes

I am learning computational geometry and just started learning the topic of quick hull algorithm for computing convex hull. I have a question, if I want to draw a set of 2D points (say 10 points) for which the algorithm will have the worst case time complexity, how will I do this? is there any easy way to find out what the points would be?

The pseudocode Of the quick hull algorithm can be found here

2
algorithmtime-complexitycomputational-geometryconvex-hull
What has your research turned up? Surely your examination of the steps of the algorithm have given you some clues. Why don't you post the pseudocode you're studying and your preliminary conclusions? – beaker
here is the pseudocode I am following : @beaker cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html – user5411115
10 points is way too low for a worst case to make sense. By the way, for a fixed number of points, all algorithms have exactly the same complexity O(1) – Yves Daoust

2 Answers

1
votes

I guess that the worst case of QuickHull is when no rejection ever occurs, i.e. when the given points form a convex polygon, and when the partitions are the most imbalanced.

So you can take points along a circle, at angles decreasing geometrically.

enter image description here

1
votes

Constructing a set of points that can generate worst-case time complexity behavior depends on the specific pseudocode you are given in the material you are studying.

The worst case complexity of Quickhull is O(N2), and the average case performance is O(NlogN). As you may have seen, Quickhull follows a divide-and-conquer strategy. Thus, achieving the latter(i.e. better) time complexity depends on being able to divide the problem into 2 similar sized (ideally equal) subproblems. If the dividing step is not balanced, and the number of elements in the 2 subproblems differ greatly, the algorithm will have to recurse N times. In other words, in each recursive step, the problem size will be reduced by a constant amount, instead of being reduced to a fraction of the original problem size.

Now, the pseudocode you provided takes the points with the lowest and highest X coordinates(i.e. leftmost and rightmost points) as bounds to divide the space into two. Ideally, this should divide the points into 2 equally large sets. But, what if this method is rendered inefficient by the specific points given as input? Then, at each step you would possibly exclude only a constant amount of points, say c, and the other half would still include N-c points. Consequently, the problem would have to recurse down O(N) steps and would end up with a quadratic complexity.

One such example, I believe, would be drawing a V shape with the points, as given below.

(0, 5)
(10, 5)
(1, 4)
(9, 4)
(2, 3)
(8, 3)
(3, 2)
(7, 2)
(4, 1)
(6, 1)
(5, 0)