Convexifying Monotonic Polygons

This website presents an algorithm for convexifying monotonic linkages in O(n2) time published in 1999. This is an important step on the way to answering the question Can any linkage be reconfigured into any other linkage with the same underlying graph?

The background section attempts to situate this algorithm in a larger context and mentions some related results. Then the problem is clearly defined before a brief explanation of the algorithm. An interactive Java applet is provided in order to allow the reader to clearly see and understand how the algorithm works. Finally, I show that the algorithm is correct and that it is guaranteed to terminate in quadratic time.

This website is mainly based on the paper Convexifying Monotone Polygons written by Biedl, Demaine, Lazard, Robbins and Soss in 1999. The curious reader is encouraged to consult this paper for a more precise proofs and some details of the algorithm ommited here, though this website is intended to provide an understanding of all the important ideas.