Skip to Main content Skip to Navigation
Conference papers

Algorithms and Geometric Constructions

Vladimir Uspenskiy 1 Alexander Shen 2 
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : It is well known that several classical geometry problems (e.g., an- gle trisection) are unsolvable by compass and straightedge construc- tions. But what kind of object is proven to be non-existing by usual arguments? These arguments refer to an intuitive idea of a geomet- ric construction as a special kind of an “algorithm” using restricted means (straightedge and/or compass). However, the formalization is not obvious, and different descriptions existing in the literature are far from being complete and clear. We discuss the history of this notion and a possible definition in terms of a simple game.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Alexander Shen Connect in order to contact the contributor
Submitted on : Tuesday, January 15, 2019 - 3:39:56 PM
Last modification on : Friday, August 5, 2022 - 3:02:59 PM


2018-cie (1).pdf
Files produced by the author(s)




Vladimir Uspenskiy, Alexander Shen. Algorithms and Geometric Constructions. CiE: Conference on Computability in Europe, Jul 2018, Kiel, Germany. pp.410-420, ⟨10.1007/978-3-319-94418-0_41⟩. ⟨lirmm-01982315⟩



Record views


Files downloads