Abstract nonsense

I was musing about the following situation a few days ago : consider a finite number of points, then take all the lines through pairs of distinct points, then all the intersection points of pairs of distinct lines, to obtain a new set of points.

There are several questions which jump to mind in such a situation :

• do we get a finite number of points? Of course!
• are there figures where we get the same points back — and only them? After a few sketches : a triangle does that.
• are the new points always in the convex hull of the first points? Again after a few sketches, a trapezoid (an arbitrary one, not a rectangle) shows it’s false (how unfortunate).
• are there situations where iterating the trick leads to a stable figure? Well, obviously the stable figures do answer that, and the example of a square shows it’s possible to start from a figure and go to a stable figure.
• are there periodical situations, that is figures where iterating gives other figures, but we fall back to the initial figure after a while? That one is trickier — if we start with strictly less than three points or aligned points, the algorithm gives zero points which is a stable situation ; if we start with at least three non-aligned, then we’ll always find the initial points in the new list of points. That means the number of points is increasing during iterations : there are no other (ultimately) periodical situations than the one discussed at the previous point. That means there are only two alternatives in that case : either the number of points is ever-increasing to infinity, or it’s ultimately stationary and we get a stable figure.
• are there figures which lead to an ever-increasing number of points? Well, I think there are trapezoids which will lead to such situations, but I didn’t try to prove it.
• given a number of points, is there a stable figure with that number of points? With at least three points (less leads to no point), the answer is yes, since we only have to align all but one (this generalizes the triangle case) — but the example of the square with a point in the middle shows it isn’t the only possibility.

Of course, trying to draw the figure with a simple hexagon was already so painful I soon realized it was beyond my poor drawing abilities (using a ruler may have helped, but hey 😉 ) — so I decided I would try to make a computer do the work for me. I decided to use haskell and its cairo bindings, since cairo is pretty easy to use, and haskell (as most functional languages) is pretty efficient when it comes to playing with lists. I quickly wrote the main code, then the viewing code. In a hundred lines I have what I need (I’m writing big).

Perhaps I’ll try to rewrite it in C++ (for performance!) or to sage. Or I’ll wait for someone to post about it on her/his blog 😉