# Maximum Intersection of Convex Partitions

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?

• @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 Feb 26, 2022 at 20:17
• 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?
– D.W.
Feb 26, 2022 at 23:09
• @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. Feb 28, 2022 at 0:12

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.