Fastest method to draw constructible regular polygons 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$
 A: 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$,


*

*Draw the circle centered at $P$ passing through $Q$.

*Draw the circle centered at $Q$ passing through $P$.
These two circles intersect at two points $R$ and $S$.

*Draw the line through $P$ and $Q$.

*Draw the line through $R$ and $S$.  These two lines are perpendicular, intersecting at a point $O$.

*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$,


*

*Draw the circle centered at $O$ passing through $P$.

*Draw the circle centered at $P$ passing through $O$. These two circles intersect at two points $A$ and $D$.

*Draw the line through $O$ and $P$. It intersects the circle from Step 1 at a point $Q$.

*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....
A: 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.
A: 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)$. 
A: 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.
A: Suppose the task is to inscribe a regular $n$-gon in a given circle. Once vertices $P_0$ and $P_i$ are located, where $i$ is coprime to $n$, the others may be found easily. It takes $O(n)$ steps to construct them, so this part of the task is more expensive, the greater $n$ is.
However, if we concentrate on that part of the task which is the location of $P_i$, this might not be harder for $n=2k$ or $n=4k$ than it is for $n=k$. Consider, for example, $n=5$ and $n=10$. Denote the pentagon's vertices by $P_i$ and the decagon's by $D_i$. Where the circumradius is $1$, the pentagon's side and diagonal $P_0P_2$ are $\sqrt{\dfrac{5\mp\sqrt5}2}$. The decagon's side and diagonal $D_0D_3$ are $\dfrac{\sqrt5\mp1}2$. The decagon's vertices $D_1, D_9$ may be found from $D_0$ thus:

Call the given circle $\Omega_1$. Draw $\Omega_1$'s diameter $D_0OD_5$. Construct radius $OB\perp OD_0$. Bisect $OB$ at $C$. Draw $D_0C$. Draw a circle with centre $C$ through $O$, cutting $D_0C$ at $D$. Draw a circle  with centre $D_0$ through $D$, cutting $\Omega_1$ at $D_1$ and $D_9$.
To get this far entails constructing 7 circles (3 to construct a perpendicular, 2 to bisect a line segment, and 2 more). This is the same as for Ptolemy's method to inscribe a regular pentagon. Indeed a regular pentagon can be inscribed using a method similar to the above for the decagon: draw $CD_5$ instead of $CD_0$, thus locating $D_4, D_6$, which are $P_2, P_3$ where $D_0$ is $P_0$. And since perpendicular radii have been constructed, the $20$-gon follows just as easily.
Inscribing a regular $17$-gon in a given circle also entails constructing perpendicular radii, one of them through the given vertex. Thus the $34$-gon and $68$-gon follow just as easily.
