Dimension++

This project is concerned with geometric partitioning structures in three-dimensional space. Frequently used such structures are triangulations, Voronoi diagrams, and straight skeletons. There is a wealth of results that are available nowadays, however, they mainly concern the two-dimensional case. In three dimensions results are quite sparse, despite the fact that quite a few practical situation lead to problems that are three-dimensional in nature. DIMENSION++ aspires to contribute to the solution of such difficult 3D questions. In particular, advance on the following three problems, which are conceptually and methodologically interrelated:(1) Voronoi diagrams for lines and line segments in 3D, especially their farthest-site variants for different metrics, and their piecewise-linear approximations.(2) Straight skeletons in 3D: in particular, the development of efficient CGAL software using a new arrangement-based algorithmic approach, and a general polytope pre-partitioning strategy based on walks on polyhedral surfaces.(3) Mitered offsets: straight-skeletal structures on triangulated surfaces in 3D, and the resulting `geodesic' proximity relations and their efficient implementation.The SNF project part concerns Problem (1). It will investigate Voronoi diagrams of lines and line segments in three dimensions (3D), which are notoriously difficult structures in the original setting, putting emphasis on the variant of the farthest-site Voronoi diagram. It aspires to answer various combinatorial, algorithmic, and approximation questions regarding these diagrams. Sample questions include: 1) Characterize the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in 3D. 2) Consider polyhedral metrics which can provide piecewise linear alternatives to the Euclidean metric. 3) Consider a tradeoff between algebraic and combinatorial complexity by sampling sets of points out of the input line segments and considering cluster Voronoi diagrams of the derived point-sets.