Algorithmic Roots of Geometry

Here are two passages from Shamos’s dissertation thesis, where he is looking at history of geometry from perspective of a computer scientist.

Egyptian and Greek geometry were masterpieces of applied mathematics. It is well established that the original motivation for tackling geometric problems was the need to tax lands accurately and fairly and to erect buildings (Eves, 72). As often happens, the mathematics that developed has permanence and significance that far transcends Pharaoh’s original revenue problem. It is a field in which intuition abounds and new discoveries are within the compass (so to speak) of amateurs.

It is popularly held that Euclid’s chief contribution to geometry was his exposition of the axiomatic method of proof, a notion that we will not dispute. More relevant to this discussion, however, is the invention of Euclidean construction, a scheman which consists of an algorithm and its proof, interwined in a highly stylized format. The Euclidean construction satisfies all of the requirements of an algorithm: It is unambiguous, correct, and terminating. After Euclid, unfortunately, geometry continued to flourish, while analysis of algorithms faced 2000 years of decline. This can be explained in part by the success of reducto ad absurdum, a technique which made it easier for mathematicians to prove the existence of an object by contradiction, rather than by giving and explicit construction for it (an algorithm).

The Euclidean construction is remarkable for other reasons as well, for it defines a collection of allowable instruments (ruler and compass) and a set of legal operations (primitives) that can be performed with them… The influence of Euclid’s Elements was so profound that it was not until Descartes that another formulation of geometry was proposed. His introduction of coordinates enabled geometric problems to be expressed as algebraic ones, paving the way for the study of higher plane curves and Newton’s calculus. Coordinates permitted a vast increase in computational power, bridged the gulf between two great areas of Mathematics, and led to a renaissance in constructivist thinking. It was now possible to produce new geometric objects by solving the associated algebraic equations…

…In 1672, Georg Mohr showed that any construction performable with ruler and compass can be accomplished with compass alone, insofar as the given and required objects are specified by points (Eves, 72). (Thus, even though a straight line cannot be drawn with compass alone, two points on the line can each be specified by intersecting two circular arcs). What is notable about Mohr’s proof is that it is a simulation, in which he demonstrates that any operation in which the ruler participates can be replaced by a finite number of compass operations. Could one ask for a closer connection with automata theory?

Michael Ian Shamos, dissertation titled “Computational Geometry”, Yale University. 1978

This dissertation is full of nice examples of relationship between problem solving issues of geometry and algorithmic thinking. It is very exciting to read after 34 years.