In 1876, Alfred Bray Kempe stated a preliminary version of what is nowadays known as Kempe‘s Universality Theorem:
For any intersection of an algebraic curve with a closed disk in the Euclidean real plane ℜ2, there is a linkage translating a motion along these curve segments to a straight line segment and vice-versa.
In my Bachelor‘s thesis, I describe the linkage design algorithm invented by Kempe, following his original publication and a more modern reformulation by Gao et al. The implementation found here accompanies the written work and provides a proof-of-concept simulation of the construction. The underlying dynamic geometry system (DGS) is Cinderella, rasterization and animation of the algebraic curves is done using Xalci.
For a introductory description of the simulation interface, please look below.
We assume that the user is familiar with the basic ideas of Kempe linkages; if this is not the case, we refer to the description in the thesis. Current DGS‘s are not capable of realizing the complete power of linkages. Basically, a linkage adapts it‘s complete structure according to the forces moving any of the bars or hinges. This amounts to simultaneously solving a (high) number of equations, which both exceeds the intention of most DGS and currently available computational capacities.
Thus, we only implement the translation from a point P on the curve to a point S on a straight line, which can be done fairly well using Cinderella‘s functionality. To achieve this, we roughly follow Kempe‘s algorithm in some major steps:
open this version in another window:
simple interface • extended interface
The most basic input required is a polynomial in ℜ[x,y], whose locus of zeroes will be the investigated curve.
We offer the choice of automatical recognition of an initial position of P on the curve.
The "(re)set P" button can also be used to move P to a distinguished position after the construction is generated.
The values m and n determine the size of the initial parallelogram linkage attached to P and thus directly influence the radius around the origin reachable by the linkwork.
The automatical adaption fits their size according to the chosen position of P.
Any change in the values requires a complete rebuild of the linkage to come into effect.
Rasterization and animation of a movement of P is done using a web backend of Xalci, and may require some time to start.
Animations tend to get very slow when a high-resolution rasterization is shown, so we recommend to use a low-resolution version.
Note that we currently cannot interrupt Cinderella during any operations, especially throughout the animation.
If operations take too long, please close the browser window and restart with a simpler case.
Due to the applet-based approach, required for the communication to Cinderella, we cannot offer the comprehensive choice of Cinderella‘s view control features. In particular, while zooming is possible, shifting the view is not. For a minimum of convenience, we thus offer the translation of the straight line S moves on to the y-axis, which is always visible regardless of the zoom level.
For more detailed investigations of the constructions, a complete log of all constructions is given in Cinderella‘s native scripting language CindyScript.
This log can be executed in a stand-alone instance of Cinderella; the resulting construction can then be investigated in all details.
Experienced Cinderella users may also use the CindyScript command line inside our program for short requests.
As mentioned, we do not try to realize the complete functionality of a linkage, i. e. we do not allow to move arbitrary hinges of the construction. But we can to some degree simulate the movement of a genuine linkwork under motion of P.
open this version in another window:
simple interface • extended interface
Since it is not possible so far to transmit information about the geometric elements from the Cinderella applet to the outside, we can hardly adapt the size of the bar lengths in the linkages to the problem instance.
In consequence, we have to stick to merely arbitrary chosen values, which turned out to leave the viewport reasonably clean.
However, some elements will not be shown for some choices of the input since the required distance of the points exceeds the fixed bar lengths; in this case, the corresponding linkages can be enlarged by dragging the semi-transparent circles around the underlying hinges.
As another drawback, angle adders (or distance copiers, in the terminology of the thesis) will only show up in the expected shape once in four times; this is due to Cinderella‘s continous geometry approach, which does not allow to arbitrarily specify positions of points by orientation or length comparisons.
Both Cinderella and the Xalci interface are still under development.
During recent tests, the Xalci backend proved to work fairly well, but minor syntactic and semantic details are subject to change, and the server may not always be reachable.
This may explain unexpected results of animation or rasterization.
The inter-applet communication to Cinderella is an early beta feature, which – except for the lack of output from Cinderella already mentioned – turned out to be very reliable.
However, in some rare cases the startup process of the two applets is disturbed, and the initial handshake for the scripting is not successful.
If this should happen (indicated by the message "CindyApplet not reachable" in the status bar), please reload the window.
Finally, inter-applet communication is not supported per default in every browser; you may have to explicitly allow this feature in the security settings of your browser.
The sources of the application, currently amounting to approximately 7300 lines of Java code, are available on request. If you are interested or want to share experiences, wishes or complaints, please contact Alexander Kobel.
Dynamic Geometry by Cinderella: http://www.cinderella.de/ (Ulrich Kortenkamp, Jürgen Richter-Gebert)
Rasterization and Animation by Xalci: http://exacus.mpi-inf.mpg.de/cgi-bin/xalci.cgi (EXACUS project, Algorithms and Complexity working group, Max-Planck-Institute for Computer Science, Saarbrücken, Germany)
© 2008 by Alexander Kobel, in partial fulfillment of the requirements for the Bachelor's degree in Computer Science.
University of Saarland, Saarbrücken, Germany
Faculty of Natural Sciences and Technology I, Department of Computer Science
Supervisor: Prof. Dr. Frank-Olaf Schreyer, advisor: Dr. Oliver Labs
Sources are available on request.
Bachelor's thesis: Automated Generation of Kempe Linkages for Algebraic Curves in a Dynamic Geometry System
This page was last updated on .