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

Improve this question
$\endgroup$
8
  • $\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
    Commented Apr 2, 2014 at 13:03
  • $\begingroup$ Ah, right, I want that the triangulation do not add additional vertices, I should add that. $\endgroup$
    – Per Alexandersson
    Commented Apr 2, 2014 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
    Commented Apr 2, 2014 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
    Commented Apr 2, 2014 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
    Commented Nov 6, 2015 at 15:53

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

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