关于QuickHull算法线性时间复杂度的两类技术问题咨询

1. Does QuickHull ever run in linear time? #

Yep, absolutely! While QuickHull is best known for its average O(n log n) runtime and worst-case O(n²) behavior, there are specific input scenarios where it runs in straight-up O(n) time. Here are two common examples:

• All points are collinear: If every point lies on a single straight line, the convex hull is just the two endpoints of that line. QuickHull starts with an O(n) scan to find the leftmost and rightmost points. When it splits the remaining points relative to the line connecting these endpoints, both resulting subsets are empty (since all other points lie directly on the line). The algorithm wraps up right after this, with total runtime O(n).
• Non-hull points are confined to a single convex hull wedge: Suppose the convex hull is a polygon, but every non-extreme point sits inside a single wedge formed by two consecutive hull vertices. Each recursive step of QuickHull will only process one non-empty subset of points, and the recursion depth stays constant (instead of logarithmic). This means every level of recursion is an O(n) scan with no branching into multiple large subproblems, leading to an overall linear runtime.

2. Can QuickHull run in linear time if the convex hull is a triangle and all non-extreme points are inside it? #

Absolutely! Let's walk through the exact flow to see why:

1. Initial extreme point scan: QuickHull first does an O(n) pass to find two extreme points—say, the leftmost (A) and rightmost (B) vertices of the triangle.
2. Finding the third hull vertex: Next, it runs another O(n) scan to find the point farthest from the line AB. Since all non-hull points are inside the triangle, this farthest point will be the third triangle vertex (C).
3. Recursive cleanup: Now the algorithm splits the remaining points into two subsets: those on the "outer" side of line AC (relative to the triangle) and those on the outer side of line BC. But since all non-hull points are inside triangle ABC, both subsets are empty. The recursive calls terminate instantly without any additional processing.

Adding up all these steps: O(n) + O(n) + O(n) = O(n) total time. The critical factor here is that there's no deep recursive branching—all non-hull points are eliminated in the initial scans, so the algorithm doesn't have to handle any large nested subproblems.

内容的提问来源于stack exchange，提问作者emon voxed