zbMATH — the first resource for mathematics

Acute triangulations of polygons. (English) Zbl 1084.68134
Summary: 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 \(\mathcal O(n^3)\) steps until all the points are in convex position.

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI