3 points are drawn on a plane, and inside their triangular region, more points are added such that no 3 are collinear, such that there are n points in total. What is the maximum possible number of line segments one could draw connecting two of these points such that none intersect other than at their endpoints?

I think Charlie got the right idea in his previous post. Certainly in the end configuration the whole region will triangulated. I think however there is minor flaw in Charlies derivation, because he assumes that the final triangulation can be gradually built up by successively adding a single point to an existing triangulations and then reconnecting the point in order to again achieve a full triangulation. However the end configuration may or may not be built up in such a way (Anyone got counter examples?). Therefore below an alternative line of thought.

From Euler's formula we know that V+F=E+2, where V, F, E denote the vertices, faces and edges respectively of the final triangulation. (Although Euler's formula is for polyhedra, it also holds for maps of this sort. In this case, the "faces" are our triangles, whereby we also have to count the infinite region outside our original triangle as a face). Because we have triangles only, we know 3F=2E. Put this into the formula above and we get E = V+2/3E-2. Solve for E and you get E = 3V-6 = 3(n+3)-6 = 3n+3.

Posted by JLo on 2006-08-18 19:24:38