Fastest method to draw constructible regular polygons

Question

We know from Gauss, that the regular polygons of order $3$, $4$, $5$, $6$, $8$, $10$, $12$, $15$, $16$, $17$, $20$, $24\ldots$ are constructible.

• Is there a provably fastest compass and straightedge method to create each (or some) of those polygons?

• If so, is the minimal number of steps (arcs and lines drawn) a known function of the number of sides?

For illustration purposes, an image of a construction of the 17-gon from Wikipedia, different from Gauss's original construction.

$\quad\quad\quad\quad$

Answer 1

Just to get the ball rolling, here is a five-step construction of a square starting from two points, which may or may not be minimal. (In comments below the OP, I gave a two-step construction for the equilateral triangle, which I daresay cannot be constructed in a single step.)

Starting with points $P$ and $Q$,

1. Draw the circle centered at $P$ passing through $Q$.
2. Draw the circle centered at $Q$ passing through $P$. These two circles intersect at two points $R$ and $S$.
3. Draw the line through $P$ and $Q$.
4. Draw the line through $R$ and $S$. These two lines are perpendicular, intersecting at a point $O$.
5. Draw a circle of arbitrary radius centered at $O$. Its intersections with the lines of Steps 3 and 4 are vertices of a square.

What's lacking here, of course, is proof that five is minimal. I hope someone will post an answer giving such a proof (or, better yet, a construction that takes fewer steps.)

Added later: Just to keep the ball rolling (and/or consume some additional low-hanging fruit), here's a four-step construction for the hexagon:

Starting with points $O$ and $P$,

1. Draw the circle centered at $O$ passing through $P$.
2. Draw the circle centered at $P$ passing through $O$. These two circles intersect at two points $A$ and $D$.
3. Draw the line through $O$ and $P$. It intersects the circle from Step 1 at a point $Q$.
4. Draw the circle centered at $Q$ passing through $O$. It intersects the circle from Step 1 at two points $B$ and $C$. The points $P,A,B,Q,C,D$ are vertices of a hexagon.

I think this is "obviously" minimal. But I think we need some explicit rules for what constitutes a construction in order to prove it's obvious....

Answer 2

Hint:

If you start from two given points and only allow to draw a straight line from two known points or a circle centered on one known point and through another, you can sketch all the possible constructions.

With a single line:

With two lines (you get the equilateral triangle):

With three lines:

With four lines (you get the hexagon):

The fifth construction with four lines shows you how to achieve the square in five lines (with an extra circle).

I conjecture that allowing to draw through unknown points would not reduce the minimum number of lines. Unfortunately, this brute force approach very quickly becomes impractical.

---

Update:

There is a missing operation: measure the distance between two known points with the compass and draw a circle with this radius around a third point.

Also, many constructions with larger circles are missing.

Answer 3

Just to add a simple observation (not an answer):

Since circles can intersect twice, whereas lines can intersect once or twice, the maximal number of intersections is given by twice the number of pairs of circles. Moreover, for a $n$-gon, clearly at least $n$ intersections are needed. Thus, a very loose lower bound is given by: $$C^2-C > n$$ Which would mean the number of steps is asymptomatically bound from below by $O\left(\sqrt{n}\right)$.

Answer 4

Just to keep the ball rolling, here is a quick way to draw the regular pentagon.

Start with a circle, centre $O$, and draw two mutually perpendicular diameters $AB$ and $CD$.

Find the midpoint of $OD$ and call it $E$.

Draw the line $BE$ extended, and bisect the angle $BEO$ both internally and externally.

These bisectors meet $AB$ at $X$ and $Y$. Construct lines perpendicular to $AB$ through $X$ and $Y$.

These perpendicular meet the circle at four points, which, together with $B$, form a regular pentagon.

I'm not sure how many steps this is according to your rules, but I would be interested to know if there is a quicker way. I doubt it.