Straight Skeletons, Polygonal and Polyhedral Offsets

Shrinking and expanding polygons and polyhedra is a rich source of important practical algorithmic problems in geometry. In prior work we gave algorithmic studies of several problems associated with polygonal offsetting. We have also developed the leading practical algorithm for computing offsets of polygonal pockets, based on our robust and efficient Voronoi skeleton code "VRONI". We propose to deepen the link between offsetting and Voronoi-like skeletons by applying our experience with skeleton-based offsetting to mitered offsetting in 2D and 3D. Contrary to the conventional offsetting based on distance functions, mitered offsetting asks to shrink or expand a polygon (in 2D) or a polyhedron (in 3D) such that the resulting shape once again is a polygon or a polyhedron, respectively. Conventional offsetting would introduce curved boundary elements, while mitered offsetting allows to remain in the original modeling domain. Among other applications, mitered offsetting has important applications in tool-path generation whenever a standard offset would cause a tool to stay in contact with a reflex vertex of the boundary for too long a time. Recent advances on linear axes and heuristics for computing mitered offsets in 2D where all sharp corners are beveled suggest that it ought to be possible to devise and implement algorithms for mitered offsetting with a better complexity than what is known so far and used in practice. Thus, we propose a practice-minded study of mitered offsetting in 2D and 3D. In order to keep our algorithms general enough we will focus on the underlying algorithmic problems rather than on specific needs within a certain application (such as tool-path generation). This approach naturally leads us to an investigation of straight skeletons and variants thereof. Although straight skeletons were proposed more than ten years ago, important questions still remain unanswered in 2D; the field is completely open for research once 3D issues are considered. We note that even for 2D applications the community still waits for a straight-skeleton code that is absolutely reliable and correct, and that can be operated as a stand- alone module. Besides working on a thorough mathematical and algorithmic foundation for mitered offsetting, we will place our emphasis on converting our algorithms into software tools, in order to jump-start future work by providing colleagues and companies with ready-to-use libraries. These tools will be implemented as small modules of their own and, thus, will be widely applicable. Hence, while being motivated by tool-path generation, several of the tools that we propose to develop will be applicable to diverse fields, including, but not limited to, CAD/CAM and GIS, thereby broadening the practical impact of the work proposed.