I am interested in the following NP-complete decision problem:Given n collections of M axis-parallel squares in the plane, is it possible to pick a single representative from each collection,such that all n representatives are pairwise disjoint?I found several useful approximation algorithms to the following maximization problem:Given n axis-parallel squares in the plane, find the largest set of pairwise disjoint squares.(see Timothy M. Chan and Sariel Har-Peled, 2013, for a recent survey of approximation algorithms for this and similar problems).I am trying to use them for solving my original problem, but in order to get a better understanding of the relation between these two problems, I ask the following theoretical question:Given an oracle that solves the maximum-disjoint-squares problem, how can it be used for solving the square-representative-decision problem?NOTE 1: The two problems can be seen as special cases of the following set packing problems:Decision problem:Given n collections of M sets, is it possible to pick a single representative from each collection,such that all n representatives are pairwise disjoint?Maximization problem:Given n sets, find the largest set of pairwise disjoint sets.In this case, there is a simple reduction from the decision problem to the maximization problem: add a unique element $A_i$ to all sets in collection $i$, find the largest set of pairwise disjoint sets, and return true if the largest set has $n$ sets. Unfortunately this reduction doesn't work in the geometric scenario.NOTE 2: Both the decision problem and the maximization problem can be solved with an oracle to the following problem:Given n collections of M axis-parallel squares in the plane,find the maximum number of disjoint representatives, one per collection.For the decision problem, just check if the maximum is $n$. For the maximization problem, take $M=1$.
Reduction from a geometric decision problem to its maximization problem
cg.comp geom;oracles;packing