5
$\begingroup$

This question is a direct generalization of:

Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices

Given a convex polytope $P \in \mathbb{R}^d,$ and a point $p\in P,$ how many simplices $S$ are there such that the $S$ is the convex hull of some $d+1$ vertices of $P$ and such that $p \in S?$

I assume that this is $\#P$-complete...

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Could you formulate this more precisely as a computational complexity problem? Otherwise, I don't think it's a real question. $\endgroup$
    – Ian Agol
    Commented Sep 9, 2011 at 14:37

1 Answer 1

Reset to default
5
$\begingroup$

There are two ways to state this question, and the answers differ.

1) Let the dimension $d$ is fixed, and the input is via $n$ vertices of the polytopes. In this case the total number of possible simplices is polynomial, and so is the counting problem.

2) If the dimension $d$ is arbitrary, everything falls apart. Think of a simplex with vertices $O=(0,\ldots,0)$ and $(0,\ldots,a,\ldots,0)$, where $a\in$ {$a_1,\ldots,a_m$}. Here $n=dm+1$. Let $z=(c,\ldots,c)$ and consider all (closed) simplices which contain $z$. Check that #simplices containing O is a variation on the #knapsack problem, several versions of which are known to be #P-complete. I omit the details.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ These are good points, though, in the interest of completeness, there is (at least) one more way to state the question: the polytope may be given by bounding hyperplanes, in which case (correct me if I am wrong), the question is not (obviously) polynomial even in fixed dimension. My guess is that is sharp-P complete then. $\endgroup$
    – Igor Rivin
    Commented Oct 19, 2011 at 9:38
  • 1
    $\begingroup$ No, actually if you have N hyperplanes, you have at most $N^d$ vertices, and thus $N^{d^2}$ possible simplices to check, polynomial again for a fixed $d$. You guess is wrong. Now, where is my "accept"? :) $\endgroup$
    – Igor Pak
    Commented Oct 20, 2011 at 0:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .