Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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...

share|improve this question
1  
Could you formulate this more precisely as a computational complexity problem? Otherwise, I don't think it's a real question. –  Ian Agol Sep 9 '11 at 14:37

1 Answer 1

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.

share|improve this answer
2  
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. –  Igor Rivin Oct 19 '11 at 9:38
1  
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"? :) –  Igor Pak Oct 20 '11 at 0:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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