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 metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01982315
Contributor : Alexander Shen <>
Submitted on : Tuesday, January 15, 2019 - 3:39:56 PM
Last modification on : Wednesday, September 4, 2019 - 5:36:03 PM

File

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

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

99

Files downloads

114