[math-fun] Triangulations of planar point sets
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.
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/ --
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/ --
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.
Hmm, what if we start by fixing the boundary of the convex hull, and add points one at a time to the interior. The *first* point inside must create a number of triangles equal to the number of vertices on the boundary. For each *successive* point: a) if it lies in the interior of a previous triangle, it adds a net of 1 point + 2 triangles. If instead we b) add a point to an interior edge, perturbing the edge slightly so it becomes 2 noncollinear segments, then again we've added: 1 point + 2 triangles So, the number T of triangles depends only on the number k of points on the boundary and the number n-k of points in the interior (assuming n > k): T = k + 2(n-k-1) = 2n-k-2. --Dan On May 30, 2014, at 7:38 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
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.
participants (3)
-
Dan Asimov -
Michael Kleber -
Tom Rokicki