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).

  • $\begingroup$ 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. $\endgroup$ – Akababa Feb 6 '18 at 4:01
  • $\begingroup$ @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)? $\endgroup$ – zwol Feb 6 '18 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.