FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA
(FUNDAMENTAL AND APPLIED MATHEMATICS)
2001, VOLUME 7, NUMBER 2, PAGES 597-614
The complexity of algorithms of constructions by compass and
straightedge
M. V. Alekhnovich
A. Ya. Belov
Abstract
View as HTML
View as gif image
View as LaTeX source
The article deals with the following problem.
Assume that there are two points and on the plane, and a
natural number is given.
Our aim is to find the third point on the line
containing and so that the length
is
times
larger than the length using only
a compass and a straightedge.
During every step we can either construct a straight line
containing two constructed points, or a circle with
a constructed point as a center and with a radius equal
to the distance between two constructed points.
Intersections of constructed lines and circles form new constructed
points.
Denote the minimal number of steps necessary to solve this
problem using only the compass as ,
and the minimal number of
steps necessary to solve this problem using both the compass and
the straightedge as .
We want to estimate the asymptotic behavior of the functions
and .
Our main result is the following: there exist constants such that a) ,
b) .
The most interesting result is obtained in connection with the lower
bound of ,
where purely algebraic notions, such as
the height of a number etc., arise quite unexpectedly.
All articles are
published in Russian.
Location: http://mech.math.msu.su/~fpm/eng/k01/k012/k01216h.htm.
Last modified: October 31, 2001.