Abstract
This paper proposes a combinatorial approach to planning non-colliding trajectories for a polygonal bar-and-joint framework with n vertices. It is based on a new class of simple motions induced by expansive one-degree-of-freedom mechanisms, which guarantee noncollisions by moving all points away from each other. Their combinatorial structure is captured by pointed pseudo-triangulations, a class of embedded planar graphs for which we give several equivalent characterizations and exhibit rich rigidity theoretic properties. The main application is an efficient algorithm for the Carpenter’s Rule Problem: convexify a simple bar-and-joint planar polygonal linkage using only non-self-intersecting planar motions. A step of the algorithm consists in moving a pseudo-triangulation-based mechanism along its unique trajectory in configuration space until two adjacent edges align. At the alignment event, a local alteration restores the pseudo-triangulation. The motion continues for O(n3) steps until all the points are in convex position.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
An erratum to this article is available at http://dx.doi.org/10.1007/s00454-006-3300-1.
Rights and permissions
About this article
Cite this article
Streinu, I. Acute Triangulations of Polygons. Discrete Comput Geom 34, 587–635 (2005). https://doi.org/10.1007/s00454-005-1184-0
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-005-1184-0