Ah, sure, of course. Thanks Tom. --Michael On Fri, May 30, 2014 at 11:03 PM, Tom Rokicki <rokicki@gmail.com> wrote:
I may not have been sufficiently clear. If you have t triangles, then you have t + 1 faces, and (3 * t + k) / 2 edges.
Plug in Euler's formula for planar graphs and solve for t.
On Fri, May 30, 2014 at 7:53 PM, Tom Rokicki <rokicki@gmail.com> wrote:
This is Euler's formula for planar graphs. Since you are splitting the hull into triangles, V and E and the number of vertices on the convex hull are related.
-tom
On Fri, May 30, 2014 at 7:38 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Okay, funsters, I'm sure this is really obvious, but I'm not figuring it out.
Take a set of points P in the plane (let's say no three collinear, just to keep it simple). A "triangulation of P" is just what you expect: a way of writing the convex hull of P as a union of triangles with disjoint interiors, such that the points of P are exactly the vertices of the triangles in the the triangulation.
Theorem, evidently: Every triangulation of P has the same number of triangles. In particular it has 2n-2-k triangles, where n = |P| and k = the number of points of P that are on the boundary of the convex hull. (Of course this means the triangulations all have the same number of edges too -- 3n-3-k of them -- thanks to Euler.)
Why is this true? I've waved my hands in the direction of some argument involving the space being connected by moves which swap diagonals of a quadrilateral, with some justification based on thinking of a triangulation as a bird's-eye view of a convex surface that's a tent with poles sitting on the points of P. But this is sounding pretty baroque and it seems like there must be something clear and simple, and I'm just not seeing it.
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.