4
$\begingroup$

Let $P$ be a convex $d$-dimensional polytope. I have two questions, related to triangulations of $P$.

Question 1: Let $p$ be in the interior of $P$. Can I always find a triangulation of $P$, such that the (or some, if not unique) $d$-dim simplex $S$ that contains $p$, has the property that $S$ intersects the boundary of $P$, such that the intersection has same dimension as the boundary of the simplex.

The triangulation should not add any additional vertices: each simplex in the triangulation must have vertices in $P$.

I think this is the property of the triangulation I wish to prove: A triangulation of $P$ is nice if every $k$-dim simplex in the triangulation has a $k-1$-dimensional intersection with a $k$-dimensional face of $P$.

Question 2: There is the notion of "pulling triangulation", used here by Stanley, which is a special type of triangulation. I suspect that this triangulation is nice, but I dont know how to prove this.

I suspect this property of the triangulation is very natural, and has most likely been studied before, so I seek some reference for this.

EDIT: For the first question, it is the same as follows:

We know that since $P$ is convex, every $p \in P$ can always be expressed as $$p = a_1p_1 + \dots + a_d p_d$$ for some $p_i \in P$ and $a_i>0$ and $\sum a_i=1$. Question 1 is equivalent to that we can always choose the $p_1,p_2,\dots,p_{d-1}$ to be vertices in a face of $P$.

$\endgroup$
  • $\begingroup$ For Q1, couldn't you triangulate so that $p$ is a vertex of every simplex, a star triangulation centered at $p$, with each simplex the hull of a facet with $p$? $\endgroup$ – Joseph O'Rourke Apr 2 '14 at 13:03
  • $\begingroup$ Ah, right, I want that the triangulation do not add additional vertices, I should add that. $\endgroup$ – Per Alexandersson Apr 2 '14 at 13:11
  • 3
    $\begingroup$ How about a star triangulation centered at some vertex $q$ of $P$ then (triangulate each face not containing $q$ and use the corresponding simplexes as bases; it looks like now every simplex has good intersection with the boundary)? $\endgroup$ – fedja Apr 2 '14 at 13:46
  • $\begingroup$ @fedja: Ah, yes, this is what my intuition tells me; is it obvious that this works? It is, right? I think the pulling triangulation of Stanley is a special case of iterated star triangulation, so, it seems to work in this case also. Is this "common knowledge" that these properties hold, or are there references for this? $\endgroup$ – Per Alexandersson Apr 2 '14 at 13:50
  • 2
    $\begingroup$ Pulling triangulations actually go back to Hudson, Piecewise Linear Topology, 1969, Lemma 1.4, and were used by various other researchers before me. $\endgroup$ – Richard Stanley Nov 6 '15 at 15:53
1
$\begingroup$

Pulling triangulations have these properties, and it is quite easy from the construction to see this.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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