This algorithm, SlowConvexHull(P), computes the convex hull of a set of points P in the plane. It's called "slow" because it has a time complexity of O(n³), where n is the number of points in P. Here's a breakdown of how it works:
1. Initialization:
E ← ∅: An empty set E is created to store the edges of the convex hull.2. Iterating Through All Point Pairs:
for all ordered pairs (p, q) ∈ P × P with p ≠ q: The algorithm iterates through all possible ordered pairs of distinct points (p, q) in P. Note that the order matters; (p, q) is different from (q, p).3. Validity Check:
valid ← true: For each pair (p, q), a flag valid is set to true initially. This flag will be used to determine if the directed edge from p to q is an edge of the convex hull.4. Checking All Other Points:
for all points r ∈ P not equal to p or q: The algorithm then iterates through all other points r in P (excluding p and q).5. Left-of Test:
if r lies to the left of the directed line from p to q: This is the core of the algorithm. It uses a "left-of" test (often implemented using determinants or cross products) to determine if the point r lies to the left of the directed line segment from p to q.6. Invalidating the Edge:
then valid ← false: If any point r is found to the left of the directed line from p to q, the valid flag is set to false. This means that the edge (p, q) cannot be an edge of the convex hull because it's "blocked" by r.7. Adding the Edge:
if valid then Add the directed edge pq to E: If, after checking all other points, the valid flag is still true, it means that no point lies to the left of the directed line from p to q. In this case, the directed edge pq is added to the set of edges E.8. Constructing the Vertex List:
From the set E of edges construct a list L of vertices of CH(P), sorted in clockwise order: After iterating through all point pairs, the set E contains the directed edges of the convex hull. The algorithm then constructs a list L of the vertices of the convex hull by following these edges in clockwise order. This step involves graph traversal.Why is it slow (O(n³))?
The algorithm has three nested loops: