Decomposition Algorithms in Geometry

Decomposing complex shapes into simpler components has always been a focus of attention in computational geometry. The reason is obvious: most geometric algorithms perform more efficiently and are easier to implement and debug if the objects have simple shapes. For example, mesh-generation is a standard staple of the finite-element method; partitioning polygons or polyhedra into convex pieces or simplices is a typical preprocessing step in automated design, robotics, and pattern recognition. In computer graphics, decompositions of two-dimensional scenes are used in contour filling, hit detection, clipping and windowing; polyhedra are decomposed into smaller parts to perform hidden surface removal and ray-tracing.