Computing Nice Sweeps for Polyhedra and Polygons
Prosenjit K. Bose, Marc J. van Kreveld · Canadian Conference on Computational Geometry · 2004
This paper does not deal with the sweeping paradigm itself; it deals with testing polygons and polyhedra to determine if they have a certain property. The properties that we consider are related to sweeping. We will test for a simple polygon or polyhedron if it can be swept by a line or plane such that every cross-section has a property like being convex or simply-connected. For example, to determine for a simple polygon (with interior) in the plane whether there is a sweep direction such that every cross-section is simplyconnected (a point, line segment, or empty) is the well-known question of determining whether a simple polygon is monotone in some direction. We solve two extensions of this problem in 3-space, and solve another extension in the plane. The first question we address applies to a polyhedron in 3space. We want to determine if there is a vector , such that if a sweeping plane with normal passes over , every cross-section of is convex. Toussaint [7] calls this property weakly monotonic in the convex sense. Obviously, for convex polyhedra, any vector gives only convex cross-sections during the sweep. For many nonconvex polyhedra no such vector exists. We give an time algorithm to find a vector if one exists, for a simple polyhedron with vertices. In case we allow more than one convex polygon in the cross-section, but no refle x vertices, we solve the problem in linear time. The second question deals with cross-sections of simple polyhedra that are always simply-connected. This property is called weakly monotonic [7]. Again the problem is to determine a vector , if one exists, such that any plane normal to intersects in a simple polygon. This cross-section may degenerate into a line segment, single point, or be empty. The cross-section may not become disconnected, nor may it contain a hole. We solve the problem in time. Thirdly, we consider sweeping a simple polygon with a line, but we allow the line to change its orientation. The problem is to determine if such a sweep exists that passes over the polygon , such that every cross-section is connected (generally, a single line segment). The problem is solved in quadratic time, also if we require additionally that the sweep line never goes back over any point of .