zbMATH — the first resource for mathematics

Convexifying monotone polygons. (English) Zbl 0964.68140
Aggarwal, Alok (ed.) et al., Algorithms and computation. 10th international symposium, ISAAC’ 99, Chennai, India, December 16-18, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1741, 415-424 (1999).
Summary: This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone polygon into a convex polygon; a polygon is monotone if any vertical line intersects the interior at a (possibly empty) interval. Our algorithm computes in \(O(n^2)\) time a sequence of \(O(n^2)\) moves, each of which rotates just four joints at once.
For the entire collection see [Zbl 0933.00045].

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)