Rotationally Monotone Polygons.
Prosenjit K. Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer · 2006
A generalization of monotonicity is introduced. An n-vertex polygon P is rotationally monotone w.r.t. a point r if there exists a partitioning of the boundary of P into exactly two polygonal chains, s.t. one chain can be ro-tated 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 rota-tion r in the plane, we determine in O(n) time whether P is rotationally monotone w.r.t. r. (2) We can find all the points in the plane from which P is rotation-ally monotone in O(n) time for convex polygons and in O(n2) time for simple polygons. Both algorithms are worst-case optimal. 1