Maximum Intersection of Convex Partitions

Question

Given a bounded, convex polytope $C \subset R^d$, I have $n$ partitions of the polytope $C$ into at most $m$ smaller polytopes (disjoint on all but sets of measure zero). These smaller polytopes have colors assigned to them. Given a color, I would like to find a point $p \in C$ such that $p$ is that color in the maximum number of partitions.

Is this setup similar to another problem I'm just not thinking of?

• Calvin Elder: @D.W. I removed the clique comment because it applied to my situation only due to some extra structure I forgot to mention. I'm now interested in solving this problem more generally, though. I also meant to say point, whoops! More proofreading next time
• D.W.: If $d$ is small, there are $O(n^d)$ time solutions, based on enumerating all possible points (by finding all intersections of all subsets of up to $d$ faces from some of the polytopes). However if $d$ is large this will be inefficient. Is this useful? Would you like me to write that as an answer?
• Calvin Elder: @D.W. Thanks, that reduction is really helpful! In my instance, n will be small (~200), whereas d has a pretty large range (100-10,000). I'll probably have to approximate it and/or formulate it differently to use an off-the-shelf solver.

Answer 1

The problem is NP-hard, by a reduction from Max-FS.

Here is the reduction. Consider any instance of Max-FS, i.e., a set of linear inequalities $A_ix \le b_i$ over $\mathbb{R}^d$. Choose a bounded polytope $C$ that is "large enough" (i.e., every intersection point of every subset of $d$ equalities $A_i x = b_i$ is in $C$). Define the $i$th partition to have two polytopes $P_i,Q_i$, where $P_i = \{x \in C : A_i x \le b_i\}$ and $Q_i = \{x \in C : A_i x \ge b_i\}$. Color every $P_i$ red. Assign each $Q_i$ a different, unique color. Now, the solution to your problem is a point $x$ that is contained in the largest number of $P_i$'s, which is the point that satisfies the largest number of linear inequalities $A_i x \le b_i$. Thus, any efficient algorithm for your problem immediately yields an efficient algorithm for Max-FS.

Since Max-FS is NP-hard, it follows that your problem is NP-hard, too.