The Complexity of Geometric Constructions

by François Labelle

straight-edge This page is about efficient constructions with straight-edge and collapsing compass (the geometric tools of Euclid). The question of what can and cannot be constructed with this model of computation is basically answered by Galois Theory. However, given that a construction is possible, there's not much to be found on the minimum number of steps required, which incidentally is the subject of this document. collapsing compass

Our Model

  1. Some points in the plane are given to start with. These points are said to be constructed.

  2. Given two constructed points, the straight-edge can be used to draw an (infinite) line through them.

  3. Given two constructed points, the collapsing compass can be used to draw a circle with center at one point and passing through the other.

  4. The points of intersection of lines and circles are considered to be constructed.
Java Applet
--> more on the model


Measure of Complexity

The complexity of a construction is defined to be the number of drawing operations (lines and circles) that are performed. Note that other complexity measures have been proposed.
--> more on complexity measures


Best Known Constructions

The main feature of this web page is a Java applet in which you can view the "best" solution (that I know of) to a variety of problems. Some solutions are just amazing!

You can also use the applet to try to solve one of the problems yourself. If you happen to beat the best known solution, tell me your solution and it will replace the old one. It's an open challenge!

Choose an applet size to go to the applet page:
--> small applet: 580 x 320
--> large applet: 850 x 520
-->
arbitrary size: x

Related Links

Euclid

Constructions Impossible (in our model)
--> paper references
This page is presented to Godfried Toussaint as a Web project for the Computational Geometry course 308-507A. Other student projects can be found here.
page created: December 5, 1997
last updated: June 7, 2014