2
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.