SlowConvexHull算法为何检查n²-n对点？3点实例的困惑

Let's break this down clearly—your confusion comes from mixing up the number of convex hull edges and the number of point pairs the SlowConvexHull algorithm checks.

First, let's recap how the naive SlowConvexHull works:

• The algorithm's core idea is to verify every possible pair of distinct points (p, q) to see if the line segment pq is an edge of the convex hull.
• To confirm this, it checks if all other points lie strictly on one side of the line pq (or exactly on the segment itself).

Why n² - n pairs? #

n² - n is equivalent to n*(n-1), which counts all ordered pairs of distinct points. For your 3-point example:

• The ordered pairs are (1,2), (2,1), (1,3), (3,1), (2,3), (3,2) — that's 6 total, which matches 3² - 3 = 6.

Why does this differ from your expected 3 pairs? #

You're thinking of the unordered convex hull edges (which are 3 for 3 points). But the SlowConvexHull doesn't start by knowing which pairs are edges—it has to check every possible ordered pair first.

Yes, (1,2) and (2,1) represent the same physical line segment, but the algorithm still considers them as separate pairs during the enumeration step. Some implementations might optimize this by only checking unordered pairs (reducing the count to n(n-1)/2), but textbooks often cite the upper bound of n² - n to simplify the time complexity analysis (since even with optimization, the algorithm is still O(n³) because each pair check requires iterating over all n-2 other points).

A concrete example with 3 points #

For each of the 6 ordered pairs:

• Check (1,2): Verify if point 3 lies on one side of the line 1→2. It does, so this is a convex hull edge.
• Check (2,1): Verify if point 3 lies on one side of the line 2→1. It does (just the opposite side of the first check), so this is also considered a valid edge (though it's the reverse of the first).
• The same logic applies to (1,3)/(3,1) and (2,3)/(3,2).

In practice, we'd deduplicate these reverse pairs to get the final 3 convex hull edges, but the algorithm still checks all 6 pairs in its brute-force approach.

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