Robust Computation Of 3D Apollonius Diagrams

Apollonius diagrams,also known as additively weighted Voronoi diagrams,are an extension of Voronoi diagrams,where the weighted distance is defined by the Euclidean distance minus the weight.Voronoi diagrams and the variants of Voronoi diagrams which include Power diagram,additively weighted Voronoi diagrams,Centroidal Voronoi Diagrams(CVT)and Centroidal Power Diagrams(CPD),have theoretical and practical applications in many fields,such as motion planning,material science,molecular biology,crystallography and computer graphics.The bisectors of Apollonius diagrams have a hyperbolic form,which is fundamentally different from traditional Voronoi diagrams and Power diagrams.Though robust solvers are available for computing 2D Apollonius diagrams,there is no robust solver for the 3D version since the latter is more complicated-the structure of a 3D Apollonius diagram has a higher combinatorial complexity and each bisector is a curved hyperbolic surface.In this thesis,we systematically analyze the structural features of 3D Apollonius diagrams,and then develop a fast algorithm for robustly computing Apollonius diagrams in 3D.Our algorithm consists of vertex location,edge tracing and face extraction,among which the key step is to adaptively subdivide the initial large box into a set of sufficiently small boxes such that each box contains at most one Apollonius vertex.Finally,we use centroidal Voronoi tessellation(CVT)to discretize the curved bisectors with well-tessellated triangle meshes.We validate the effectiveness and robustness of our algorithm through extensive evaluation and experiments.We also demonstrate an application on computing centroidal Apollonius diagram.This thesis makes the following contributions:1.A systematical analysis of the topological and geometric features of 3D Apollonius diagrams and a full discussion on degenerate cases.2.A fast algorithm for computing 3D Apollonius diagrams.The key idea is to adaptively subdivide an initial large box into a set of sufficiently small boxes such that each box contains at most one Apollonius vertex.3.A computational tool for representing 3D Apollonius diagrams using welltessellated triangle meshes that can benefit the downstream applications in digital geometry processing.