Algorithms and Geometric Constructions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2018

Algorithms and Geometric Constructions


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.
Fichier principal
Vignette du fichier
2018-cie (1).pdf (336.95 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01982315 , version 1 (15-01-2019)



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⟩
81 View
123 Download



Gmail Facebook X LinkedIn More