Computing the Voronoi cells of planes, spheres and cylinders in

Abstract: We present an algorithm for computing the Voronoi cell for a set of planes, spheres and cylinders in . The algorithm is based on a lower envelope computation of the bisector surfaces between these primitives, and the projection of the trisector curves onto planes bounding the object for which the Voronoi cell is computed, denoted the base object. We analyze the different bisectors and trisectors that can occur in the computation. Our analysis shows that most of the bisector surfaces are quadric surfaces and five of the ten possible trisectors are conic section curves. We have implemented our algorithm using the IRIT library and the Cgal 3D lower envelope package. All presented results are from our implementation. [Copyright &y& Elsevier]