This is my problem:

There are n collections of M geometric shapes (not necessarily disjoint).
Pick a single shape from each collection,
     such that the n selected shapes are pairwise interior-disjoint.

This problem is NP-complete even when the shapes are restricted to axis-parallel squares (see this cstheory.SE question ). The naive algorithm is to check all $M^n$ combinations in the cartesian product. Assuming we can check intersection of two shapes in time O(1), the naive algorithm takes time $O(n\cdot M^n)$. What heuristics can be used to reduce the run-time?

NOTE: About 2 months ago I asked a related question, in which there is only a single collection of candidate shapes. In that case, I used a geometerically-based divide-and-conquer heuristic, combined with branch-and-bound as recommended by D.W. Careful tuning lead to a dramatic reduction in run-time (50-80 times faster).

However, I don't see a way to use divide-and-conquer in the current problem. I can partition the collections, but, a disjoint set in one partition won't necessarily be compatible with a disjoint set in the other partition (the sets might contain shapes from the same collection...)

Can you suggest any heuristics, either divide-and-conquer or otherwise, for solving this problem more efficiently?


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.