Theory
- Draw several figures of near-triangulations similar to the
ones below, including at least 2 of them with B > 5 and I >
10.
In each case, show that it is possible, using just 3 colors, to color the triangles in the figure, as shown in the figure below, so that triangles that share an edge get different colors.
- Prove that we can 3-color the triangles in any such
near-triangulation. Note that this is relatively easy to prove by
induction, if the vertex you remove (in order to use the induction
hypothesis) is on an edge, or near an edge.
-
When done, some triangles will be oriented consistently clockwise, or consistently counter-clockwise. In the above figure, five of them are oriented consistently, and seven of them are not. Use problem 2 to prove that it is always possible to orient the edges so that there are at least twice as many consistent triangles as inconsistent triangles.Suppose that we take a near-triangulation and put a direction on each edge in the figure, as shown here
Program
Your task is to identify all the triangles produced by the triangulations generated by this code.
I would prefer that you modify the code that I give to you, rather than using your own. That said, however, you may use your own code if you have a strong preference to do so. If you do, please make any additions necessary so that:
- The points are graphically numbered somehow, as in my program
- So that when you print your triangles, to System.out, I can quickly see whether you've correctly identified the triangles or not.