20051201
Generalizing monotonicity: On recognizing special classes of polygons and polyhedra
Publication
Publication
International Journal of Computational Geometry and Applications , Volume 15  Issue 6 p. 591 608
A simple polyhedron is weaklymonotonic in direction d→ provided that the intersection of the polyhedron and any plane with normal d→ is simplyconnected (i.e. empty, a point, a linesegment or a simple polygon). Furthermore, if the intersection is a convex set, then the polyhedron is said to be weaklymonotonic in the convex sense. Toussaint10 introduced these types of polyhedra as generalizations of the 2dimensional notion of monotonicity. We study the following recognition problems: Given a simple nvertex polyhedron in 3dimensions, we present an O(n log n) time algorithm to determine if there exists a direction d→ such that when sweeping over the polyhedron with a plane in direction d→, the crosssection (or intersection) is a convex set. If we allow multiple convex polygons in the crosssection as opposed to a single convex polygon, then we provide a lineartime recognition algorithm. For simplyconnected crosssections (i.e. the crosssection is empty, a point, a linesegment or a simple polygon), we derive an O(n2) time recognition algorithm to determine if a direction d→ exists. We then study variations of monotonicity in 2dimensions, i.e. for simple polygons. Given a simple nvertex polygon P, we can determine whether or not a line ℓ can be swept over P in a continuous manner but with varying direction, such that any position of ℓ intersects P in at most two edges. We study two variants of the problem: one where the line is allowed to sweep over a portion of the polygon multiple times and one where it can sweep any portion of the polygon only once. Although the latter problem is slightly more complicated than the former since the line movements are restricted, our solutions to both problems run in O(n2) time.
Additional Metadata  

Duality, Monotone, Plane sweep, Polygon, Polyhedra  
dx.doi.org/10.1142/S0218195905001877  
International Journal of Computational Geometry and Applications  
Organisation  School of Computer Science 
Bose, P, & Van Kreveld, M. (Marc). (2005). Generalizing monotonicity: On recognizing special classes of polygons and polyhedra. International Journal of Computational Geometry and Applications, 15(6), 591–608. doi:10.1142/S0218195905001877
