Finding a "complete" convex hull in less than O(n^2)

Question

I have not been very successful in googling this issue, since most convex hull discussions assume you want a minimal bounding box and are very vague about how to fill this minimal hull boundary to a "complete" hull. Here "complete" simply means that any points that lie on minimal convex hull edges are added to the convex hull.

To make matters clear, here's a very simple example. Assume that we have n=9 vertices in 2D space. I will index them from 0 to 8 for simplicity.

[0] = (0; 0)
[1] = (0; 1)
[2] = (0; 2)
[3] = (1; 0)
[4] = (1; 1)
[5] = (1; 2)
[6] = (2; 0)
[7] = (2; 1)
[8] = (2; 2)

We can find the minimal bounding box with Graham scan in O(nlogn). There are other algorithms that do it in O(nlogh), but let's keep things simple for a start. The minimal hull is [0, 2, 6, 8] (or [0, 8, 6, 2]; this does not really matter). The "complete" hull would be all vertices except [4]. How should I post-process the minimal hull to achieve the "complete" hull without increasing the complexity to O(n^2)?

Obviously, changing the GS algorithm to include collinear points (>0 to >=0 or <0 to <= 0) is not going to work. Must I use another algorithm?

Oh, and another thing: for the sake of this question, please assume h ~= n, so that O(n * h) is effectively O(n^2).

---

Since people refused to believe that my provided example causes GS to fail when changing the vertex product comparison to include zero. Here's the explanation of the counterexample:

1. Find a corner point by whatever means (doesn't really matter if you do it as wiki says, which is lowest Y, then lowest X, or first lowest X and then lowest Y, or inverted order)

2. Add corner to convex hull

3. Sort remaining points by their polar angles (once again, it does not matter if it's done over the Ox or Oy axis, as long as all the actions are adjusted properly)

These pairs of points will have equal polar angles: [1, 2], [3, 6], [4, 8]. If you allow them to be lined up arbitrarily, this will definitely kill GS, due to the fact that you may attempt 0 6 3 7, after which GS will permanently remove 3 from the convex hull as an invalid vertex (same applies to the [1, 2] pair).

Typical polar angle equality tiebreaker is, as I have seen, ordering them based on their distance from the corner point. However, if you will decide to order points with farther distance first, then GS will have to take 0 6 3 7, which marks 3 as non-hull point. On the other hand, if you sort to have points with closer distance to the corner point, you will take [...] 5 1 2 0, which will cause GS to mark 2 as a non-hull point.

The question was, can we fix this by an elaborate polar angle sorting strategy OR postprocessing.

Answer 1

Here's an O(log h)-time algorithm that, given a convex hull with h vertices in sorted order and a query point, tests whether the query point lies on the hull. From the hull, compute a point in the interior by averaging three of its vertices. Call this point the origin. Partition the plane into wedges bounded by rays from the origin through hull vertices. Use binary search with an orientation test to determine which wedge the query point belongs to. Test whether it lies on that wedge's hull segment.

If you've already implemented the Graham scan, then it is possible to retain collinear points just by changing the test, but you need to determine angles relative to an origin point that is not collinear with two other hull points. Such a point can be obtained by taking the mean of three input points that are not collinear.

Answer 2

After some thinking, I figured out that when you change the comparison to include 0, and break ties by (closer first) distance to corner point (or even simply by comparing coordinates), then only the last edge is affected, specifically it skips the edge points.

In your example, indeed you end up considering points 5, 1 and 2, but the algorithm will skip point 1 rather than 2 (since 5-1-2 is a clockwise turn), so the resulting hull is 0 3 6 7 8 5 2.

One simple way to deal with that is to go through the sorted points in reverse order and add to the hull all points collinear with your corner and the last hull point, until you get to a non-collinear point.

There could be a special case when all points are collinear - it depends whether you want to include the edge points twice (forward and back) or just once.