Voronoi Diagrams for Oriented Spheres

F. Aurenhammer, M. Peternell, H. Pottmann, and J. Wallner

Abstract:

We consider finite sets of oriented spheres in (k-1)-space and, by interpreting such spheres as points in k-space, study the Voronoi diagrams they induce for several variants of distance between spheres. We give bounds on the combinatorial complexity of these diagrams in the plane and in 3-space, and derive properties useful for constructing them. Our results are motivated by applications to special relativity theory.

Reference: F. Aurenhammer, M. Peternell, H. Pottmann, and J. Wallner. Voronoi diagrams for oriented spheres. In Proc. 4th Int. Symp. on Voronoi Diagrams in Science and Engineering, ISVD'07, pages 33-37, Pontypridd, UK, 2007.