All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Shapes > Geometry
Points on a plane (Posted on 2006-08-18) Difficulty: 3 of 5
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?

No Solution Yet Submitted by atheron    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution How Leonhard would solve it | Comment 2 of 5 |
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information