Abstract
Straightedge-and-compass construction problems are well known for different reasons. One of them is the difficulty to prove that a problem is not constructible: it took about two millennia to prove that it is not possible in general to cut an angle into three equal parts by using only straightedge and compass. Today, such proofs rely on algebraic tools difficult to apprehend by high school student. On the other hand, the technique of problem reduction is often used in theory of computation to prove other kinds of impossibility. In this paper, we adapt the notion of reduction to geometric constructions in order to have geometric proofs for unconstructibility based on a set of problems known to be unconstructible. Geometric reductions can also be used with constructible problems: in this case, besides having constructibility, the reduction also yields a construction. To make the things concrete, we focus this study to a corpus of triangle location problems proposed by William Wernick in the eighties.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Anglesio, J., Schindler, V.: Solution to problem 10719. Am. Math. Mon. 107, 952–954 (2000)
Beeson, M.: Constructive geometry. In: Arai, T. (ed.) Proceedings of the Tenth Asian Logic Colloquium, pp.19–84.World Scientific, Singapore (2010)
Buthion, M.: Un programme qui résout formellement des problèmes de constructions géométriques. RAIRO Informatique. 3(4), 353–387 (1979)
Chen, G.: Les constructions à la règle et au compas par une méthode algébrique. Technical Report Rapport de DEA, Université Louis Pasteur (1992)
Connelly, H.: An extension of triangle constructions from located points. Forum Geom. 9, 109–112 (2009)
Connelly, H., Dergiades, N., Ehrmann, J.-P.: Construction of triangle from a vertex and the feet of two angle bisectors. Forum Geom. 7, 103–106 (2007)
Danneels, E.: A simple construction of a triangle from its centroid, incenter, and a vertex. Forum Geom. 5, 53–56 (2005)
DeTemple, D.W.: Carlyle circles and the lemoine simplicity of polygon constructions. Am. Math. Mon. 98(2), 97–108 (1991)
Djorić, M., Janičić, P.: Constructions, instructions, interactions. Teach. Math. Appl. 23(2), 69–88 (2004)
Fursenko, V.B.: Lexicographic account of triangle construction problems (part i). Math. Sch. 5, 4–30 (1937, In Russian)
Fursenko, V.B.: Lexicographic account of triangle construction problems (part ii). Math. Sch. 6, 21–45 (1937, In Russian)
Gao, X.-S., Chou, S.-C.: Solving geometric constraint systems. i. A global propagation approach. Comput. Aided Des. 30(1), 47–54 (1998)
Gao, X.-S., Chou, S.-C.: Solving geometric constraint systems. ii. a symbolic approach and decision of rc-constructibility. Comput. Aided Des. 30(2), 115–122 (1998)
Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman, New York (1979)
Graver, J., Servatius, B., Servatius, H.: Combinatorial rigidity. Graduate Studies in Mathematics, vol. 2. American Mathematical Society (1993)
Grima, M., Pace, G.J.: An embedded geometrical language in Haskell: construction, visualisation, proof. In: Computer science annual workshop (2007)
Gulwani, S., Korthikanti, V.A., Tiwari, A.: Synthesizing geometry constructions. In: Programming language design and implementation, PLDI 2011, pp 50–61. ACM (2011)
Janičić, P.: URSA: a system for uniform reduction to SAT. Log. Methods Comput. Sci. 8(3:30): 1–39 (2012)
Jermann, C., Trombettoni, G., Neveu, B., Mathis, P.: Decomposition of geometric constraint systems: a survey. Int. J. Comput. Geom. Appl. 16(5–6), 379–414 (2006, CNRS MathSTIC)
Lopes, L.: Manuel de construction de triangles. In: Boucherville (ed.) QED Texte, Québec (1996)
On-line compendium of triangle construction problems with automatically generated solutions. Teach. Math. XVIII(1), 29–44 (2015)
Marinkovic, V.: ArgoTriCS—automated triangle construction solver. J. Exp. Theor. Artif. Intell. (2016). doi: 10.1080/0952813X.2015.1132271
Marinković, V., Janičić, P.: Towards understanding triangle construction problems. In: Jeuring, J., et al. (eds.) Intelligent computer mathematics—CICM 2012, Lecture Notes in Computer Science, vol. 7362. Springer (2012)
Marinković, V., Janičić, P., Schreck, P.: Computer theorem proving for verifiable solving of geometric construction problems. In: Automated deduction in geometry 2014, Lecture Notes in Computer Science, vol. 9201, pp. 72–93. Springer (2015)
Martin, G.E.: Geometric constructions. Springer (1998)
Meyers, L.F.: Update on William Wernick’s triangle constructions with three located points. Math. Mag. 69(1), 46–49 (1996)
Scandura, J.M., Durnin, J.H., Wulfeck II, W.H.: Higher order rule characterization of heuristics for compass and straight edge constructions in geometry. Artif. Intell. 5(2), 149–183 (1974)
Schreck, P.: Constructions à la règle et au compas. PhD thesis, University of Strasbourg (1993)
Schreck, P.: Modélisation et implantation d’un système à base de connaissances pour les constructions géométriques. Revue d’intelligence artificielle 8(3), 223–247 (1994)
Schreck, P., Mathis, P.: RC-constructibility of problems in Wernick’s list. In: Proceedings of the 10th International workshop on automated deduction in geometry (ADG 2014), pp. 85–104. CISUC Technical Report TR 2014/01, University of Coimbra (2014)
Specht, E.: Wernicks liste (in Deutsch). http://hydra.nat.uni-magdeburg.de/wernick/
Stewart, I.: Galois theory. Chapman and Hall Ltd (1973)
Ustinov, A.V.: On the construction of a triangle from the feet of its angle bisectors. Forum Geom. 9, 279–280 (2009)
Wernick, W.: Triangle constructions vith three located points. Math. Mag. 55(4), 227–230 (1982)
Yiu, P.: Elegant geometric constructions. Forum Geom. 5, 75–96 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
V. Marinković and P. Janičić were supported by the Grant ON174021 of the Ministry of Science of Serbia.
Rights and permissions
About this article
Cite this article
Schreck, P., Marinković, V. & Janičić, P. Constructibility Classes for Triangle Location Problems. Math.Comput.Sci. 10, 27–39 (2016). https://doi.org/10.1007/s11786-016-0255-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11786-016-0255-3