An axiomatic approach to voronoi-diagrams in 3D

摘要

Voronoi-diagrams were first introduced for sets of points, and later generalized to other sets. There have been very few attempts to generalize Voronoi-diagrams for non-point sets to three (or higher) dimensions. We define a Voronoi-diagram for a quite general subset of three-space which is characterized by specific axioms. This diagram is one-dimensional and connected provided that the complement of the subset is connected. These Voronoi-diagrams can be used in retraction methods to solve the Findpath Problem for a ball moving in a three-dimensional environment.