# Choosing the optimal nonempty intersection from a list of pairs of shapes

Suppose an ordered list of ordered pairs of plane shapes. The list is finite, each individual shape is finite, and all of the shapes lie within a finite rectangle. However, the shapes themselves are not simple polygons; they may be concave, they may have holes, and they may even be disconnected. (In the specific application I have in mind, I think the shapes that can actually happen are one polygon with no holes, one polygon with one interior hole, and two polygons with no holes; in all cases the polygons and holes may be convex or concave. But I could have missed something.)

For each pair $(a,b)$, shape $b$ may be equal to shape $a$, or $b$ may be a larger version of $a$, with the same centroid (sort of) (this can be made rigorous but only by explaining in detail how the shapes are generated, and I would like to avoid getting into that). It follows that $a \subseteq b$ always. The list is ordered by the areas of the $a$ shapes: for any two pairs $(a_i, b_i)$ and $(a_j, b_j)$, if $i < j$ then the area of $a_i$ is less than or equal to the area of $a_j$. Note that the analogue does not necessarily hold for the $b$ shapes.

The intersection of all the $b$ shapes is nonempty. However, the intersection of all the $a$ shapes is empty. The problem is to choose one of $a$ and $b$ from each pair such that the intersection of all of the chosen shapes is nonempty, while using as many of the $a$ shapes as possible (note that this does not mean "the intersection should be as small as possible"), as efficiently as possible.

This can be brute-forced by testing all possible choices, but there are $2^n$ of them and $n \sim 100$, so that's not going to fly. One can cut the list down a bit by skipping the cases where $a = b$ and discarding the cases where an $a$ fails to overlap the intersection of all $b$, but both of those should be rare.

This problem has enough structure that I feel there must be a more efficient method, but the only thing I can think of is to take the intersection of all the $b$ shapes and then replace them one at a time with $a$ shapes and see if that produces an empty intersection, and I'm fairly sure that doesn't actually work (for instance, if there is an $a$ shape in a bad location early in the list, this method could get stuck on intersections that include that shape, when more $a$ shapes could be used without it).

• The $b$ shapes can be almost anything, so in the worst case you would have to test the intersections of all $2^n$ subsets anyway. – Akababa Feb 6 '18 at 4:01
• @Akababa Does it help if I tell you that each $b$ shape is always an enlarged version of the corresponding $a$ shape, with the same centroid (sort of)? – zwol Feb 6 '18 at 13:29