Rotationally monotone polygons
We introduce a generalization of monotonicity. An n-vertex polygon P is rotationally monotone with respect to a point r if there exists a partitioning of the boundary of P into exactly two polygonal chains, such that one chain can be rotated clockwise around r and the other chain can be rotated counterclockwise around r with neither chain intersecting the interior of the polygon. We present the following two results: (1) Given P and a center of rotation r in the plane, we determine in O(n) time whether P is rotationally monotone with respect to r. (2) We can find all the points in the plane from which P is rotationally monotone in O(n) time for convex polygons and in O( n2) time for simple polygons. We show that both algorithms are worst-case optimal by constructing a class of simple polygons with Ω( n2) distinct valid centers of rotation. A direct application of rotational monotonicity is the popular manufacturing technique of clamshell casting, where liquid is poured into a cast and the cast is removed by rotations once the liquid has hardened.
|Keywords||Monotonicity, Rotational casting, Simple polygon|
Bose, P, Morin, P, Smid, M, & Wuhrer, S. (Stefanie). (2009). Rotationally monotone polygons. In Computational Geometry (Vol. 42, pp. 471–483). doi:10.1016/j.comgeo.2007.02.004