Computational compass-and-straightedge constructions

Question

I recently came across Ancient Greek Geometry, a web toy by Nico Disseldorp, and it got me wondering: is there a way to exactly model the points generated by geometric constructions, starting from two distinct points, in a way that allows performing computations on them?

I would need finite representations of:

• points,
• lines specified by two points, and
• circles specified by the center and a point on the circumference

such that the intersection points of any two constructible objects can be computed. Though objects do not need unique representations, it must be possible to compute whether two representations refer to the same object.

Is there a way to represent constructible points, lines, and circles in this way?

Answer 1

Is there a way to represent constructible points, lines, and circles in this way?

It is, but it is far from trivial to implement. The first thing that came to mind when I saw your question, was the data structures used in the Dynamic Geometry program EucliDraw, which I happen to have seen.

I do recall that any geometry document which has suffered any number of alterations (including not only ruler and compass transformations but also non-euclidean ones) could be unfolded into a huge tree, with roots the three elements you are inquiring about and branching down into leaves representing the final state of things, including figures and relations between figures, etc.

The complete tree structure is fairly complicated even for simple drawings, and it is hard to examine by eye, but internally of course is used to do many of the things you inquire, like finding intersections, total number of coincidences, recognizing shapes, etc.

In short, it is doable on the Complex plane, but the details are fairly hairy.