Approximations of 3D Generalized Voronoi Diagrams

Abstract

We introduce a new approach to approximate generalized 3D Voronoi diagrams for different site shapes (points, spheres, segments, lines, polyhedra, etc) and different distance functions (Euclidean metrics, convex distance functions, etc). The approach is based on an octree data structure denoted Voronoi-Octree (VO) that encodes the information required to generate a polyhedral approximation of the Voronoi diagram. Since the medial axis of a polyhedron is a subset of a generalized Voronoi diagram the VOcan also be used to encode it. Using the information of the VOwe generate and visualize a polyhedral approximation of a generalized Voronoi diagram, and we also solve proximity problems that do not require an explicit representation of the Voronoi diagram such as nearest neighbor queries.