Math.Comput.Sci. DOI 10.1007/s11786-017-0308-2

Mathematics in Computer Science

Real-time Animated Dynamic Geometry in the Classrooms by Using Fast Gröbner Basis Computations Zoltán Kovács

Received: 26 November 2016 / Revised: 21 February 2017 / Accepted: 8 March 2017 © Springer International Publishing 2017

Abstract Real-time animation of loci and envelopes in dynamic geometry software may be challenging because of the high amount of heavy symbolic computations being performed continuously. This paper reports on reaching 30 frames per second (FPS) in the desktop application GeoGebra for non-trivial examples for immediate use in classrooms—also 13 FPS is reached in a modern web browser. Keywords Mathematics education · Locus · Envelope · Gröbner bases · Computer graphics · Animation Mathematics Subject Classification Primary 97G40; Secondary 14H50

1 Introduction The second millennium renaissance of elementary geometry by harnessing software applications in the classroom is already history. By introducing dynamic geometry (DG) systems like The Geometer’s Sketchpad [15], Cabri [19] or Cinderella [29] the high number of mechanical numerical computations enabled students to make their own experiments with geometric objects easily—including investigating loci or envelopes. Today’s computers go one step forward. Not only fast numerical computations are available, but symbolic commands help, for instance, to expand or factorize expressions or solve equations or equation systems. Nevertheless, application of symbolic computations in DG remained an unexplored field for many years. Recent researches in the direction to compute Gröbner bases (GB) significantly faster than earlier,1 opened the road to manipulate on tens of equation systems in several variables within a second. Thus now it is possible to create realtime animations based on symbolic computations. Such real-time animations include computing locus or envelope equations for geometry constructions on various software platforms like native Java programs, web applications or mobile/tablet solutions. In this paper some recent technical results will be demonstrated in the GeoGebra [18] dynamic mathematics tool which fully connects computer algebra systems (CAS) and DG. By computing and visualizing the algebraic 1

See [20,26] for two studies on the open source computer algebra systems.

Z. Kovács (B) The Private University College of Education of the Diocese of Linz, Salesianumweg 3, 4020 Linz, Austria e-mail: [email protected]

Z. Kovács

equation of a non-trivial locus 30 frame per second (FPS) can be reached on an Intel Core i7-2620M CPU @ 2.70GHz desktop computer (with 8 GB RAM installed, Ubuntu Linux 14.04.4). The same benchmark reaches 13 FPS as a web application in Google Chrome 52.0.2743.82. On the structure of this paper: Sect. 2 explains the computation flow of a geometric locus or envelope in GeoGebra. Section 3 gives an overview how the current results are achieved. Section 4 reports an analysis of the graphical use of these novel tools and summarizes some possible improvements. Finally, the Appendix uncovers some computational details on the concrete GB computations. 2 Computation Flow of the Visual Experiments Classroom application of the used technology is mainly on discovering general properties of geometry diagrams. GeoGebra—like many other DGS tools—makes it possible to construct a figure by using objects like points, lines or circles, and then, for example, GeoGebra’s LocusEquation command calculates the equation of a locus (given by the tracer and mover points) and plots that as an implicit curve. When the user drags the free points of the diagram, the locus equation will be automatically recomputed using heavy symbolic computations, but due to the effectivity of the calculations, the equation will be obtained very quickly. Finally the implicit curve will be plotted by using numerical methods, based on the symbolic form of the equation. To summarize the above: GeoGebra’s computation flow consists of 1. 2. 3. 4.

Collecting the user’s input, Translating the input to an algebraic equation system (algebraization), Symbolic manipulation on the equation system by using effective computer algebra, Plotting the obtained curve (or discrete points) by a fast numerical algorithm (output),

finally, if the user continues the experiments, this process will restart (see Fig. 1): the user interacts by dragging one of the input points. A similar scenario is to create the envelope equation of a set of output paths while the moving point is bound to another object. (An envelope is a curve that is tangent to each member of the family of the output paths at some point.

Fig. 1 Computation flow

Real-time Animated DG in the Classrooms

Fig. 2 An activity for young learners: Join the numbers on each ray by a segment to make sums 16. Now the envelope of the rays is a curve that is tangent to each ray at some point. By using GeoGebra (or some basic algebra), it turns out that the envelope is a parabola [10,21]. This activity is also called ‘string art’

A basic example, borrowed from an Austrian mathematics textbook [13] for 10 years old students, can be seen in Fig. 2.) Obtaining the envelope is possible by using the Envelope command in GeoGebra. While computing a locus requires elimination and factorization only, envelope computations may also need derivatives and the determinant of a Jacobian matrix. (See [11] on the computational details how one can obtain an envelope by using algebraic equations.) Recently another form of the LocusEquation command was introduced in GeoGebra [1], namely which calculates the locus of the free point such that a Boolean condition is satisified. This new form is also known as implicit locus equation. Due to the possibility to its direct use in the education, this third form seems to be the most fruitful method to harness symbolic computations under the hood in a DG experiment. For example, a natural way to discover Thales’ theorem in the classroom is to construct a triangle ABC with GeoGebra, and then type the command LocusEquation[a ⊥ b,C]. In this way the circle with diameter AB will be immediately obtained and quickly redrawn when the free points A or B are dragged (Fig. 3). Further examples are shown in [22,23]. All the three visualization activities above are common in using computational algebraic geometry to manipulate on coordinates of points, and their output is always an algebraic curve (or the union of discrete points) which is computed by—roughly speaking—eliminating some variables in the algebraic translation of the geometric construction: • For the explicit locus, this is performed by denoting the locus point by (x, y), and the other points of the construction by (vi , vi + 1) for some i, and the relationships among the points are described by polinomial f j (v1 , v2 , . . . , vn , x, y) = 0. Now the goal is to eliminate all variables but x and y from the ideal  equations fj . • For the envelope computation we start with the same steps, but we define the locus point virtually by putting it on the object which is tangent to the envelope. Now by computing the determinant of the Jacobian matrix   ∂f  1 ∂ f2 · · · ∂ fn   ∂v1 ∂v1 ∂v1   ∂ f1 ∂ f2 ∂f   ∂v2 ∂v2 · · · ∂vn2   D= . .. ..  .. .  .. . .   ∂ f1 ∂ f2 ∂ f n   · · · ∂vn ∂vn ∂vn

Z. Kovács

Fig. 3 An imaginary classroom discovery of Thales’ theorem while dragging point B from (3, 1) to (4, 3). Tracing is switched on for point B and implicit curve d to illustrate animation presented as static media

an extra f n+1 = D will be obtained. As a final step, we eliminate all variables but x and y from the   polynomial ideal f j . • For the implicit locus, the sought mover point is denoted by (x, y), and the other points of the construction by (vi , vi + 1). The relationships among the points are described by the polynomial equations f j = 0: they are the hypotheses. The algebraic translation of the assumed implicit condition   (the thesis) is also added to the polynomials. Now by eliminating all variables but x and y from the ideal f j the implicit locus will be obtained. (See Appendix for a detailed example.) The elimination process in GeoGebra is performed by one or two of the best available open source2 implementations, notably the standalone CAS Singular and the embedded system Giac. On the other hand, the main bottleneck of the computations is obviously the elimination step. To obtain the sought implicite curve one needs heavy GB computations which are known to be doubly exponential in the number of variables [4]. When computing envelopes another bottleneck may appear: the size of the Jacobian matrix should be kept as low as possible to avoid explosion of computations for the determinant. This may be achieved by consecutively removing all variables vi if there is a linear polynomial f j of vi among the equations. (The same idea is used in [28] for speeding up eliminations, among others.) 2

In many classrooms open source solutions are preferred due to financial reasons.

Real-time Animated DG in the Classrooms

Fig. 4 A generalization of the Steiner-Lehmus theorem by entering LocusEquation[h == i,A] where h and i are two internal angle bisector segments of triangle ABC. Actually, for the algebraic background here GeoGebra solves the following question: for which points A in the plane will be h or h  equal to i or i  where h  and i  are the respective external angle bisector segments of the triangle. The obtained result is not just the bisector of BC but also BC itself plus a remarkable curve which is a degree 10 polynomial. See [27] as well

Here we mention two slow implicit locus examples. A moderately slow test case is shown at [22] as example “Bisector via angles (isosceles triangle)”—in GeoGebra’s web version, unfortunately, the free points in the diagram cannot be dragged because Giac runs out of resources. A much slower example is shown in Fig. 4—it is a recent generalization of the Steiner–Lehmus theorem (see Table 2 for details.) Luckily, many classroom questions remain manageable: [7] provides a list of more than 50 test cases on locus equations and [25] shows some envelope demonstrations. The need to use symbolic computations instead of numerical ones in certain DG visualization tasks is well discussed in the literature, see [9], Sect. 3 for more details. Thus all of the mentioned visualization activities are of the same kind: they require fast GB computations under the hood. It is important to mention that factorization usually helps in plotting the implicit curve in a better quality. GeoGebra uses an implementation of the quadtree algorithm [16] to plot implicit curves quickly, but it may produce some incorrect details if its input is not in a squarefree and irreducible form (see Sect. 4 for some more challenges on plotting.)

3 GeoGebra: Collaborative Work The LocusEquation command was introduced in 2010 in GeoGebra’s development version by the pioneer work of Botana’s, Abánades’, Escribano’s and Arbeo’s [8,10]. They implemented automatic translation of a Euclidean geometric construction into an algebraic equation system. The elimination step was implemented by outsourcing the computations to the computer algebra system JAS first, and later to Reduce, Singular and recently to Giac [26]. The visualization step of the locus equation as an implicit curve was implemented by Birklbauer and Drakuli´c [6] in 2011. Further improvements on the LocusEquation command were based on the joint work of the pioneers, and Montes’ and Recio’s [3]. Envelope support was added later by Botana and Kovács [9] in 2013. Implementation of the implicit locus equation was achieved by Abánades, Botana, Kovács, Recio and Sólyom-Gecse in 2016 (see [2] for a collection of examples).

Z. Kovács

Fig. 5 Stress test at GeoGebra Materials to measure the current FPS value in GeoGebra’s web version for an implicit locus animation in Google Chrome. The graph below shows the actual FPS value

4 Benchmark and Future Work GeoGebra’s built-in maximal animation speed is 30 FPS3 which is one of the main rate standards in the TV and digital camera business [31]. While the desktop application ensures this speed for many non-trivial classroom theorems (see [21] for some examples), there may be issues when using the web version of GeoGebra: Fig. 5 shows only about 13 FPS which seems to be the maximal animation speed while automatically dragging point A on line f and updating the output of the command LocusEquation[a + b == 5,C]4 . By contrast, Fig. 6 shows much better results for the desktop mode. Without any doubt the web version may require further improvements. Its slowness depends on the JavaScript technology which offers usually one magnitude slower execution than running the same algorithm in a Java Virtual Machine (JVM). To achieve faster results the underlying CAS should be embedded by using different technology, maybe WebAssembly [14]. 3

See https://dev.geogebra.org/trac/browser/trunk/geogebra/common/src/main/java/org/geogebra/common/kernel/AnimationMana ger.java for details. See https://www.geogebra.org/m/Y9pvktxx#material/RUU96uH4 to run the benchmark in a browser after clicking the  icon. It uses the GeoGebra API method getFrameRate(). See https://www.geogebra.org/manual/en/Reference:JavaScript for more details.

4

Real-time Animated DG in the Classrooms

Fig. 6 FPS graph for the desktop version of the same benchmark as in Fig. 5

Fig. 7 The triangle ABC is regular and point D is to be found such that f + g == h. Now LocusEquation[ f + g == h,D] delivers all possible points D such that f + g = h or g + h = f or h + f = g since in elimination theory no difference can be made between “positive” or “negative” lengths. Clearly, the curve (in red) looks inaccurate in the neighborhood of B

Another possible improvement would be to fix the following issue: Factorization of the polynomial of an implicit curve to irreducible polynomials having integer coefficients may be insufficient in some cases, because sometimes there may be factors with irrational coefficients. GeoGebra’s CAS Giac currently does not have an internal algorithm to find the absolute factorization [5] in such cases, that is it leaves the polynomial in expanded form. An example 2 y 2 + 3x 2 − 6x y 2 + 3y 4 − y 2 = 0 is a product of presented at [21] is shown in Fig. 7: the output 3x 4 − 6x 3 + 6x √ √ two circles, namely x 2 + y 2 + 33 y − x = 0 and x 2 + y 2 − 33 y − x = 0 (and the multiplier constant 3). But there will still another problem remain. In some cases the quadtree algorithm cannot deal with squarefree, irreducible curves, either. Such an example is a pretzel curve (Fig. 8, [17]). A possible workaround would be to convert the implicit curve to a parametric curve, but this does not seem to be achievable easily [30]. In this paper the focus was on the current technical possibilities. A mandatory question still remains: How introducing geometric animations improve the students’ understanding? One possible approach to use implicit curves to support students’ conjectures is summarized in [23]. On the other hand, further analysis on direct classroom uses, benefits and reports on effectiveness of these visual extensions are still to be done. One of the next steps of

Z. Kovács

Fig. 8 Given a circle with center A and circumpoint M, radius r . Let B be another circumpoint and C a point on line AB. What is the O r locus of points C such that M AO = BC ? Now LocusEquation[M O/AO == r/BC,C] delivers a product of a pretzel curve and a parabola, and they both are plotted independently. But the pretzel curve intersects itself in 3 different points, and the final output looks inaccurate in their neighborhood

the on-going research is to evaluate and improve GeoGebra’s contribution to teaching geometry by using the novel technology [12].

Appendix Lastly some more details on the computations are provided. A typical implicit locus equation for the construction shown in Fig. 7 is computed in GeoGebra in Table 1. In this example 5 numbered polynomials have been set up for the hypotheses and 4 for the thesis. Also 8 additional equations set up the axes. Since B(v13 , v14 ) has concrete co-ordinates for one given locus, v13 = 1 and v14 = 0 will be substituted in each polynomial (on a user interaction, later, when B on the x-axis is dragged by the user, different substitutions will be performed for v13 , while v14 remains 0). Then a GB for the ideal I will be computed with respect to total degree reverse lexicographical ordering to eliminate v1 and v2 —they are the coordinates of D

Real-time Animated DG in the Classrooms Table 1 GeoGebra log messages during translating the geometry construction to a polynomial ideal

These pieces of debug information can be printed by running GeoGebra with the command line options --logfile=/dev/stdout and --loglevel=TRACE on a Linux system. See also [20], p. 271, for more details on starting GeoGebra with parameters on other operating systems

(for technical reasons GeoGebra uses v1 and v2 instead of x and y in its internal computations). I consists of 17 polynomials: I = −v7 v6 + v8 v5 + v7 v4 − v5 v4 − v8 v3 + v6 v3 , −v11 v10 + v12 v9 + v11 v4 − v9 v4 − v12 v3 + v10 v3 , −v8 2 2 2 2 2 +v6 − v7 v6 + v8v 5, 1 − v16 − v15 + 2v16 v4 − 2v3 + 2v15 v3 , −v16 + 2v15 − v15 + v42 − 2v3 + v32 , v17 2 2 2 2 −v16 − v15 + 2v16 v2 − v22 + 2v15 v1 − v12 , v18 − v42 − v32 + 2v4 v2 − v22 + 2v3 v1 − v12 , −1 + v19 − v22 + 2v1 4 2 2 4 2 2 2 2 4 −v12 , v19 − 2v19 v18 + v18 − 2v19 v17 − 2v18 v17 + v17 , v6 , v8 , v5 , −1 + v7 , −v9 , −v11 , v10 , −1 + v12 . (4.1)

Z. Kovács Table 2 Benchmarking a single frame in the examples of this paper in various open source CAS Test

CoCoA-5

Giac

Maxima

Singular

String art (Fig. 2)

0.01

0.05

0.18

0.01

Thales (Fig. 3)

0.00

0.04

0.04

0.00

FPS (Fig. 5)

0.00

0.04

0.09

0.00

Figure 8

0.01

0.04

0.68

0.01

Bisector via angles (isosceles triangle)

0.33

0.35

4.26

0.00

Generalized Steiner–Lehmus (Fig. 4)

1.30

0.85

Timeout

0.49

Numbers are in seconds. Timeout was 60 s

Performing the same GB computations with recent versions of CoCoA-5 (CoCoALib-0.99543), Giac (1.2.2– 103), Maxima (5.37.2–8) and Singular (4.0.3) by using [24] we obtain timings 0.01, 0.04, 0.26 and 0.00 seconds, respectively. This clearly means that these systems may perform 100, 25, 4 and more than 100 FPS theoretically for this single frame, respectively. For the other examples it is also possible to run benchmarks by using [24]. Table 2 shows the results by using the inputs added in commits 497fdaf and c24bc29. It needs to be mentioned that CoCoA-5 was started without its internal libraries to save about 0.1 second on startup time. Since each system was started for each test separately, these results should be improved if the systems are embedded. Maxima seems to be significantly slower on more difficult computations than the other systems. This means that careful selection of the underlying CAS is important when planning a workflow for real-time animations. On the other hand, CoCoA-5, Giac and Singular are all good candidates to ensure continuous animation as backend computation systems. By embedding them into a higher level user interface as libraries, like in GeoGebra, they promise positive user experience. This list contains however only selected examples. Also certain CAS may have special improvements during the GB computations when the elimination is directly requested,5 that is, the results could be even better than listed. That is, these results could be refined by further research by adding more tests and changing the investigated algorithms to direct implementations of the elimination process.

References 1. Abánades, M.Á., Botana, F., Kovács, Z., Recio, T., Sólyom-Gecse, C.: Development of automatic reasoning tools in GeoGebra. ACM Commun. Comput. Algebra 50, 85–88 (2016) 2. Abánades, M.Á., Botana, F., Kovács, Z., Recio, T., Sólyom-Gecse, C.: Implicit loci. A GeoGebraBook. http://tube.geogebra.org/ m/mbXQuvUV (2016) 3. Abánades, M.Á., Botana, F., Montes, A., Recio, T.: An algebraic taxonomy for locus computation in dynamic geometry. Comput. Aided Des. 56, 22–33 (2014) 4. Bardet, M.: On the complexity of a Gröbner basis algorithm. In: INRIA Seminars. http://algo.inria.fr/seminars/summary/ Bardet2002.pdf (2002) 5. Bertone, C., Chèze, G., Galligo, A.: Modular Las Vegas algorithms for polynomial absolute factorization. J. Symb. Comput. 45(12), 1280–1295 (2010) 6. Birklbauer, P., Drakuli´c, D.: Implicit curves. In: Second International GeoGebra Conference, Hagenberg, Austria. http:// ggbconference2011.pbworks.com/w/file/fetch/44873718/presentation (2011) 7. Borcherds, M.: Locus Line Equations Demos. A GeoGebraBook. https://www.geogebra.org/b/aUSaUvmp (2016) 8. Botana, F., Kovács, Z.: Teaching loci and envelopes in GeoGebra. A GeoGebraBook. http://tube.geogebra.org/m/R8nUbEQV (2014) 9. Botana, F., Kovács, Z.: A Singular web service for geometric computations. Ann. Math. Artif. Intell. 74(3), 359–370 (2015) 5

This is the case also for Giac, see [28].

Real-time Animated DG in the Classrooms 10. Botana, F., Kovács, Z.: New tools in GeoGebra offering novel opportunities to teach loci and envelopes. arXiv:1605.09153 [cs.CG] (2016) 11. Botana, F., Recio, T.: Computing envelopes in dynamic geometry environments. Ann. Math. Artif. Intell. pp. 1–18 (2016) 12. Botana, F., Recio, T., Vélez, M. P.: The role of automated reasoning of geometry statements in mathematics instruction. In: Poster at the CERME-10 Conference, Dublin, Ireland (2017) 13. Boxhofer, E., Huber, F., Lischka, U., Panhuber, B.: MathematiX 1. Veritas Verlag, Linz (2013) 14. Bright, P.: The Web is Getting its Bytecode: WebAssembly. Ars Technica, Condé Nast (2015) 15. De Villiers, M.: Exploring Loci on Sketchpad, Pythagoras, 46(47), Mathematical Association of Southern Africa: August/December 1998, pp. 71–73 (1998) 16. Finkel, R., Bentley, J.L.: Quad trees: a data structure for retrieval on composite keys. Acta Inform 4(1), 1–9 (1974) 17. Hašek, R., Kovács, Z., Zahradník, J.: Loci problems in age of reason and their effect on GeoGebra—locus equations and their factorization in GeoGebra. In: International GeoGebra Conference, Budapest, Hungary. http://test.geogebra.org/~kovzol/talks/ igi14/bp (2014) 18. Hohenwarter, M.: GeoGebra: Ein Softwaresystem für dynamische Geometrie und Algebra der Ebene. Master’s thesis, Paris Lodron University, Salzburg, Austria (2002) 19. Jahn, A.P.: Locus and Trace in Cabri-géomètre: relationships between geometric and functional aspects in a study of transformations. ZDM 34(3), 78 (2002) 20. Kovács, Z.: Computer based conjectures and proofs in teaching Euclidean geometry. PhD thesis, Johannes Kepler University, Linz, Austria (2015) 21. Kovács, Z.: RT animated DG in the classrooms by using fast GB. A GeoGebraBook. https://www.geogebra.org/m/Y9pvktxx (2016) 22. Kovács, Z.: Variations on implicit loci in a triangle. A GeoGebraBook. https://www.geogebra.org/m/gH3b2Vwa (2016) 23. Kovács, Z.: Implizite Ortslinien in GeoGebra, e-Didaktik conference, Linz. https://www.geogebra.org/m/afpvF72v (2016) 24. Kovács, Z.: gbt (Gröbner basis tests). A GitHub project. https://github.com/kovzol/gbt (2016) 25. Kovács, Z.: Envelopes. A GeoGebraBook. https://www.geogebra.org/m/HEyFxCvA (2016) 26. Kovács, Z., Parisse, B.: Giac and GeoGebra—-improved Gröbner basis computations, In: Computer Algebra and Polynomials, Volume 8942 of the series Lecture Notes in Computer Science, pp. 126–138 (2015) 27. Losada, R., Recio, T., Valcarce, J. L.: On the automatic discovery of Steiner-Lehmus generalizations, In: Proceedings of ADG’2010, Lecture Notes in Computer Science, Springer, München, pp. 171–174 (2010) 28. Parisse, B.: About Giac’s Gröbner basis and ideal elimination computation, Presentation at the 22nd Conference on Applications of Computer Algebra Kassel, Germany. http://test.geogebra.org/~kovzol/guests/BernardParisse/aca16-parisse. (2016) 29. Richter-Gebert, J., Kortenkamp, U.H.: User Manual for the Interactive Geometry Software Cinderella. Springer, Berlin (2000) 30. Sendra, J. R., Winkler, F., Perez-Diaz, S.: Rational Algebraic Curves—A Computer Algebra Approach. Springer, Berlin, Heidelberg, ISBN 978-3-540-73724-7 (2008) 31. Wikipedia contributors, Frame rate, Wikipedia, The Free Encyclopedia. (2016). Accessed 25 Nov 2016