1
$\begingroup$

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?

$\endgroup$

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.