×

zbMATH — the first resource for mathematics

Constructibility classes for triangle location problems. (English) Zbl 1342.51017
Summary: 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 W. Wernick [Math. Mag. 55, 227–230 (1982; Zbl 0497.51016)].

MSC:
51M15 Geometric constructions in real or complex geometry
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
GCLC; URSA; ArgoTriCS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anglesio, J; Schindler, V, Solution to problem 10719, Am. Math. Mon., 107, 952-954, (2000)
[2] Beeson, M.: Constructive geometry. In: Arai, T. (ed.) Proceedings of the Tenth Asian Logic Colloquium, pp.19-84.World Scientific, Singapore (2010) · Zbl 1193.03021
[3] Buthion, M.: Un programme qui résout formellement des problèmes de constructions géométriques. RAIRO Informatique. 3(4), 353-387 (1979) · Zbl 0403.51014
[4] 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)
[5] Connelly, H, An extension of triangle constructions from located points, Forum Geom., 9, 109-112, (2009) · Zbl 1168.51302
[6] 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) · Zbl 1120.51008
[7] Danneels, E, A simple construction of a triangle from its centroid, incenter, and a vertex, Forum Geom., 5, 53-56, (2005) · Zbl 1069.51014
[8] DeTemple, DW, Carlyle circles and the Lemoine simplicity of polygon constructions, Am. Math. Mon., 98, 97-108, (1991) · Zbl 0745.51011
[9] Djorić, M; Janičić, P, Constructions, instructions, interactions, Teach. Math. Appl., 23, 69-88, (2004)
[10] Fursenko, V.B.: Lexicographic account of triangle construction problems (part i). Math. Sch. 5, 4-30 (1937, In Russian) · Zbl 0860.51014
[11] Fursenko, V.B.: Lexicographic account of triangle construction problems (part ii). Math. Sch. 6, 21-45 (1937, In Russian)
[12] Gao, X-S; Chou, S-C, Solving geometric constraint systems. i. A global propagation approach, Comput. Aided Des., 30, 47-54, (1998)
[13] Gao, X-S; Chou, S-C, Solving geometric constraint systems. ii. a symbolic approach and decision of rc-constructibility, Comput. Aided Des., 30, 115-122, (1998)
[14] Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman, New York (1979) · Zbl 0411.68039
[15] Graver, J., Servatius, B., Servatius, H.: Combinatorial rigidity. Graduate Studies in Mathematics, vol. 2. American Mathematical Society (1993) · Zbl 0788.05001
[16] Grima, M., Pace, G.J.: An embedded geometrical language in Haskell: construction, visualisation, proof. In: Computer science annual workshop (2007)
[17] Gulwani, S., Korthikanti, V.A., Tiwari, A.: Synthesizing geometry constructions. In: Programming language design and implementation, PLDI 2011, pp 50-61. ACM (2011)
[18] Janičić, P.: URSA: a system for uniform reduction to SAT. Log. Methods Comput. Sci. 8(3:30): 1-39 (2012)
[19] 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) · Zbl 1104.65304
[20] Lopes, L.: Manuel de construction de triangles. In: Boucherville (ed.) QED Texte, Québec (1996) · Zbl 0745.51011
[21] On-line compendium of triangle construction problems with automatically generated solutions. Teach. Math. XVIII(1), 29-44 (2015)
[22] Marinkovic, V.: ArgoTriCS—automated triangle construction solver. J. Exp. Theor. Artif. Intell. (2016). doi: 10.1080/0952813X.2015.1132271
[23] 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)
[24] 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)
[25] Martin, G.E.: Geometric constructions. Springer (1998) · Zbl 0890.51015
[26] Meyers, LF, Update on william wernick’s triangle constructions with three located points, Math. Mag., 69, 46-49, (1996) · Zbl 0860.51014
[27] Scandura, JM; Durnin, JH; Wulfeck, WH, Higher order rule characterization of heuristics for compass and straight edge constructions in geometry, Artif. Intell., 5, 149-183, (1974) · Zbl 0288.68051
[28] Schreck, P.: Constructions à la règle et au compas. PhD thesis, University of Strasbourg (1993)
[29] Schreck, P, Modélisation et implantation d’un système à base de connaissances pour LES constructions géométriques, Revue d’intelligence artificielle, 8, 223-247, (1994)
[30] 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)
[31] Specht, E.: Wernicks liste (in Deutsch). http://hydra.nat.uni-magdeburg.de/wernick/
[32] Stewart, I.: Galois theory. Chapman and Hall Ltd (1973) · Zbl 0269.12104
[33] Ustinov, AV, On the construction of a triangle from the feet of its angle bisectors, Forum Geom., 9, 279-280, (2009) · Zbl 1177.51019
[34] Wernick, W, Triangle constructions vith three located points, Math. Mag., 55, 227-230, (1982) · Zbl 0497.51016
[35] Yiu, P, No article title, Elegant geometric constructions. Forum Geom., 5, 75-96, (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.