How do you handle collinear points in the gift wrapping algorithm?

2 The collinear points problem

The gift wrapping algorithm assumes that there are no three points in P that are collinear, or lie on the same line. If there are collinear points, the algorithm may produce incorrect or inconsistent results. For example, consider the following set of points: P = {(0,0), (1,0), (2,0), (3,0), (2,1), (1,2), (0,3)} The points (0,0), (1,0), (2,0), and (3,0) are collinear. If we apply the gift wrapping algorithm to P, we may get different convex hulls depending on which point is chosen as the next point when the current point is (0,0). If we choose (1,0), we get the convex hull: {(0,0), (1,0), (3,0), (2,1), (1,2), (0,3)} If we choose (3,0), we get the convex hull: {(0,0), (3,0), (2,1), (1,2), (0,3)} Both convex hulls are valid, but they are not the same. This can cause problems if we want to compare or use the convex hulls for other purposes.

3 The collinear points solution

One possible solution to handle collinear points in the gift wrapping algorithm is to modify the angle comparison criterion. Instead of choosing the point that makes the smallest angle with the previous segment of the rope, we can choose the point that is farthest from the current point along the same direction. This way, we can skip over the intermediate collinear points and get a consistent convex hull. The pseudocode for the modified gift wrapping algorithm is:

Input: A set of points P
Output: A list of points that form the convex hull of P
Find the leftmost point L in P and add it to the output list
Set the current point C to L
Repeat
  Set the next point N to the first point in P
  For each point Q in P
    If Q is not N and (Q is on the left of the line segment CN or Q is collinear with CN and farther from C than N)
      Set N to Q
  Add N to the output list
  Set C to N
Until C is L        

4 The collinear points example

Let's apply the modified gift wrapping algorithm to the same set of points as before: P = {(0,0), (1,0), (2,0), (3,0), (2,1), (1,2), (0,3)} The algorithm starts from the leftmost point (0,0) and chooses the farthest point along the same direction, which is (3,0). Then it chooses the point that is on the left of the line segment (0,0)(3,0), which is (2,1). Then it chooses the point that is on the left of the line segment (3,0)(2,1), which is (1,2). Then it chooses the point that is on the left of the line segment (2,1)(1,2), which is (0,3). Finally, it returns to the starting point (0,0) and stops. The convex hull is: {(0,0), (3,0), (2,1), (1,2), (0,3)} This convex hull is the same as the one we got when we chose (3,0) as the next point in the original gift wrapping algorithm. However, this solution is more robust and does not depend on the order of the points in P.

5 The collinear points complexity

The modified gift wrapping algorithm has the same time and space complexity as the original gift wrapping algorithm. The time complexity is O(nh), where n is the number of points in P and h is the number of points in the convex hull. The space complexity is O(h), since we only need to store the output list. The modified gift wrapping algorithm is still a simple and intuitive way to find the convex hull of a set of points in the plane, but it can handle collinear points more consistently and reliably.

6 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?