Find the largest convex black area in an image

Question

I have an image of which this is a small cut-out:

As you can see it are white pixels on a black background. We can draw imaginary lines between these pixels (or better, points). With these lines we can enclose areas.

How can I find the largest convex black area in this image that doesn't contain a white pixel in it?

Here is a small hand-drawn example of what I mean by the largest convex black area:

P.S.: The image is not noise, it represents the primes below 10000000 ordered horizontally.

Answer 1

I'll sketch a correct, poly-time algorithm. Undoubtedly there are data-structural improvements to be made, but I believe that a better understanding of this problem in particular will be required to search very large datasets (or, perhaps, an ad-hoc upper bound on the dimensions of the box containing the polygon).

The main loop consists of guessing the lowest point p in the largest convex polygon (breaking ties in favor of the leftmost point) and then computing the largest convex polygon that can be with p and points q such that (q.y > p.y) || (q.y == p.y && q.x > p.x).

The dynamic program relies on the same geometric facts as Graham's scan. Assume without loss of generality that p = (0, 0) and sort the points q in order of the counterclockwise angle they make with the x-axis (compare two points by considering the sign of their dot product). Let the points in sorted order be q₁, …, q_n. Let q₀ = p. For each 0 ≤ i < j ≤ n, we're going to compute the largest convex polygon on points q₀, a subset of q₁, …, q_{i - 1}, q_i, and q_j.

The base cases where i = 0 are easy, since the only “polygon” is the zero-area segment q₀q_j. Inductively, to compute the (i, j) entry, we're going to try, for all 0 ≤ k ≤ i, extending the (k, i) polygon with (i, j). When can we do this? In the first place, the triangle q₀q_iq_j must not contain other points. The other condition is that the angle q_kq_iq_j had better not be a right turn (once again, check the sign of the appropriate dot product).

At the end, return the largest polygon found. Why does this work? It's not hard to prove that convex polygons have the optimal substructure required by the dynamic program and that the program considers exactly those polygons satisfying Graham's characterization of convexity.