Modified Quickhull algorithm for finding convex hulls

153 Views Asked by At

The quickhull algorithm described here finds the furthers point from the line segment in step 3. I am having trouble reasoning about what would be the result if the algorithm just considered the maximum y-coordinate instead. I think it would still yield the correct answer just possibly with more points lying outside the triangle described in step 4. Is this reasoning correct? I also believe I read somewhere that points with the same x-coordinates are chosen by considering the maximum y-coordinate which might have pushed me to this conclusion.

1

There are 1 best solutions below

2
On BEST ANSWER

Imagine that the point with max $y$ is actually the leftmost point. Then you get $0$ points in the upper part. But at the same time there could be many there (especially if your line is tilted very much).