Complete automation of trajectory planning tools for material deposition/removal applications has become increasingly necessary to reduce the "concept-to-consumer" timeline for rapid product introduction in industries such as the automotive industry. The work in this paper is specifically motivated by automotive spray painting. Prior developments in automated trajectory planning tools promise to reduce the time required to program the robots; however, these approaches are limited to surfaces that are either approximately planar or topologically simple (i.e., with no holes). To extend the applicability of these planning tools to nonplanar and topologically complex surfaces, currently the user has to manually segment a complex surface into simpler subsets, i.e., subsets that are approximately extruded surfaces and contain no holes. However, the complex nature of the relationships between surface segmentation and resulting output characteristics such as material deposition uniformity, process cycle time, and material waste makes the task of manually segmenting the surface difficult. In this paper, we develop a hierarchical procedure that automatically segments a surface based on surface geometry, surface topology, and path geometry to obtain topologically simple subsets that are approximately extruded surfaces. Finally, we compare the effectiveness of our segmentation with the state of the art on a few automotive surfaces in simulation. Note to Practitioners--The surface segmentation strategies described in this work can be applied to surfaces that are composed of approximately extruded surface patches joined together by regions of high curvature; such surfaces include typical automotive surfaces. The segmentation procedure allows the user to automatically generate a collection of preliminary coverage trajectories. With careful selection and minor clean up, these trajectories can improve the coverage uniformity for a given surface. The procedure operates on a surface CAD model, preferably in the triangulated manifold format and requires information about the material distribution (or removal) pattern produced from the atomizer (or machining) tool. With an understanding of the relative costs associated with different output characteristics such as uniformity of deposition, cycle time, and material waste, the procedures can be incorporated in existing industrial planning and simulation toots (with appropriate support from the software vendor) for applications such as robotic spray painting and CNC machining. [ABSTRACT FROM AUTHOR]