How to render a circle with as few vertices as possible?

In case you want to draw the polygon triangles from the center of the circle, the formula for the required number of sides is:

sides = PI / arccos(1 - error / radius)

where error is the maximum deviation of polygon from the circle, in pixels and radius is also expressed in pixels.

Error 0.33 seems to produce results indistinguishable from an ideal circle. Circles drawn at error 0.5, on close inspection still show some subtly visible angles between sides, especially visible in small circles.

This function obviously breaks down when radius is much smaller than error, and may produce NaN values. You may want to use a special case (for example draw 3 sides) in this situation.

The graph below shows number of sides obtained from the function, with error set to 0.33:

The answer you link to actually implements exactly the idea you propose at the end of your question.

The decisive formula that you need from that answer is this one:

th = arccos(2 * (1 - e / r)^2 - 1)

This tells you the angle between two vertices, where r is the radius of the circle and e is the maximum error you're willing to tolerate, i.e. the maximum deviation of your polygon from the circle -- this is the error marked in your diagram. For example, you might choose to set e to 0.5 of a pixel.

Because th is measured in radians, and 360 degrees (a full circle) is equal to 2*pi in radians, the number of vertices you need is

num_vertices = ceil(2*pi/th)

First of all, if you are using OpenGL or DirectX you can significantly decrease the number of vertices by using a triangle fan structure.

As for the problem of the amount of vertices, I would imagine the number of vertices required for a smooth circle to scale with the circumference. This scales with r, so I would advice to find a good factor A such that:

#vertices = A * r