Generalized Weighted Voronoi Diagrams for Variable-Radius Of

A Voronoi diagram is a geometric structure studied in the field of computational geometry which features a wide range of real-world applications in science and industry. Roughly, the Voronoi diagram of point sites in the plane tessellates the plane into interior-disjoint regions. Each so-called Voronoi region is given by the loci of all points in the plane which have this site as the closest one. Voronoi diagrams have been generalized in several different ways, such as using a distance measure other than the standard Euclidean distance, choosing different types of input sites instead of just points, or assigning both additive and multiplicative weights to sites. One of the more prominent applications of (unweighted) Voronoi diagrams of straight-line segments and circular arcs is the efficient generation of (constant-radius) offset curves and offset areas. In prior work we have studied weighted skeletal structures in order order to use them as tools for the geometric characterization and efficient computation of constant-radius and mitered offset curves of arbitrary planar straight-line graphs. Among other applications, such an offset can be used to model the area painted during the movement of an artists brush if a uniform pressure of the brush is applied. If, however, the artist applies a non-uniform pressure then a so-called variable-radius offset corresponds to the area covered by paint, and the currently known algorithms to model constant-radius or mitered offsets are no longer applicable. In this project we intend to study the interaction of variable-radius offsets with a skeletal structure which captures the geometry of variable-radius offsets: generalized weighted Voronoi diagrams. That is, we propose to apply our experience with weighted skeletal data structures to (1) generalized weighted Voronoi diagrams, and (2) variable-radius offsets of planar straight-line graphs in the plane. In a nutshell, our goal is to provide full algorithmic support for variable-radius offsets for the first time. Besides working on a thorough mathematical and algorithmic foundation for generalized weighted Voronoi diagrams and variable-radius offsets, 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 genuine algorithmic problems of computational geometry, the tools that we propose to develop will be applicable to diverse fields, including, but not limited to, CAD/CAM, architecture and GIS, thereby broadening the practical impact of the work proposed.

Computational geometry is a field of (theoretical) computer science that is concerned with the efficient solution of problems that bear a geometric flavor. Voronoi diagrams form a key data structure of computational geometry; they provide the algorithmic basis for efficient solutions to a variety of geometric problems in diverse fields of application, ranging from tool-path planning in CAD/CAM to shape reconstruction in medical imaging, roof modeling in architecture, the computation of centerlines of roads and rivers in geographic information systems, and even to habitat modeling in zoology. Roughly, the Voronoi diagram of a set S of points in the Euclidean plane can defined and computed by the prairie-fire analogy: Suppose that fires start in all points of S at the same time, spreading out uniformly in all directions at unit speed. A point in the plane ("prairie") then belongs to the Voronoi region of the point of S whose fire reached it first. The loci where two fire waves meet make up the edges of the Voronoi diagram. The actual fire waves form instances of the (constant-radius) offset curves of the points for specific offset distances. We can influence the spreading of the fire waves by letting the fires expand at different speeds and by starting them at different times. The same conceptual approach can be used not just for points, but also for more general input sets like straight-line segments. Basically, the circular wave fronts of the fires ignited at points get replaced by wavefronts for the straight-line segments whose form resembles bicycle chains. The result of this process are generalized weighted Voronoi diagrams. In this project we worked out the mathematical and algorithmical details of generalized weighted Voronoi diagrams. Furthermore we investigated the computation of individual wave fronts. (These wave fronts are known as "offsets" in the CAD/CAM community and as "buffers" in the GIS community.) We also devised implementations of all our algorithms in the programming language C++. Some of our implementations are based on standard IEEE 754 floating-point arithmetic while others are based on exact arithmetic provided by the Computational Geometry Algorithms Library (CGAL). In any case, our codes are provided free of charge on the platform GitHub. (GitHub is an online service that offers storage space and a version control system for software projects.) At the time of writing of this summary, our work has already attracted attention and has led to a new cooperation with an international company. The large number of inquiries received in the past on similar work gives us confidence that the results of this project will soon be in wide-spread use across a large variety of scientific fields and in industrial applications.