PLAYING WITH TRIANGULATIONS

Metamorphosis of the Triangulation Coloring Game

An Animated Proof Sketch

Introduction

Let S be a set of n points in the plane, which are assumed to be in general position, i. e., no three points of S lie on the same line.
A triangulation of a point set S in the plane, is a maximal planar straight line graph, where the vertices of the graph are the points of S. Here, each face is a triangle.

Triangulation Coloring Game

Two players move in turn by coloring a black edge of the triangulation T(S) green.
The first player who completes an empty green triangle wins.
This game was introduced by Aichholzer et al. [ABD+03].

Example 1: Simple Path Dual

The First Metamorphosis

Example 2: Simple Branching Tree Dual

The Second Metamorphosis

The Game Kayles

The Last Incarnation

Introduced by Dudeney and independently also by Sam Loyd, who originally called it 'Rip Van Winkle's Game'.
Description [BCG01]: Each player, when it is his turn to move, may take 1 or 2 beans from a heap, and, if he likes, split what is left of that heap into two smaller heaps.

References

[ABD+03]
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia, "Geometric Games on Triangulations", in Proceedings of the 19th European Workshop of Computational Geometry, Bonn, Germany, March 24-26, 2003, to appear.
[BCG01]
E.R.Berlekamp, J.H. Conway, R. K. Guy, "Winning Ways for your Mathematical Plays", Academic Press (1982). Second edition in print, A K Peters Ltd., (2001).

Gerhard Trippen

HOME
Last modified: Fri Jul 25 17:31:31 CST 2003