05012007

j

05012007 Bose, Prosenjit van Kreveld, Marc Generalizing monotonicity: On recognizing special classes of polygons and polyhedra. Int. J. Comput. Geom. Appl. 15, No. 6, 591-608 (2005). 2005 World Scientific, Singapore EN polyhedra polygon plane sweep duality monotonicity recognition algorithm Zbl 0588.68053

doi:10.1142/S0218195905001877

The paper deals with the problems of recognizing whether or not polygons and polyhedra have a certain property related to monotonicity. A simple polyhedron is weakly-monotonic in direction $\vec d$ provided that the intersection of the polyhedron and any plane with normal $\vec d$ is simply-connected (i.e. empty, a point, a line-segment or a simple polygon). Furthermore, if the intersection is a convex set, then the polyhedron is said to be weakly-monotonic in the convex sense. {\it G. T.\,Toussaint} [Computational geometry, Mach. Intell. Pattern Recognition 2, 335--375 (1985; Zbl 0588.68053)] introduced these types of polyhedra as generalizations of the 2-dimensional notion of monotonicity. The authors study the following recognition problems: Given a simple $n$-vertex polyhedron in $\Bbb R^3$, they present an $O(n\log n)$ time algorithm to determine if there exists a direction $\vec d$ such that when sweeping over the polyhedron with a plane in direction $\vec d$, the cross-section (or intersection) is a convex set. For simply-connected cross-sections (i.e. the cross-section is empty, a point, a line-segment or a simple polygon), they derive an $O(n^{2})$ time recognition algorithm to determine if a direction $\vec d$ exists. Then they study variations of monotonicity in 2-dimensions, i.e. for simple polygons. Given a simple $n$-vertex polygon $P$, the authors can determine whether or not a line $\ell$ can be swept over $P$ in a continuous manner but with varying direction, such that any position of $\ell$ intersects $P$ in at most two edges. Vladimir Yu. Rovenskij (Nesher)