K-voronoi diagrams computing in arbitrary domains

Abstract

We propose a novel algorithm to compute Voronoi diagrams of order k in arbitrary 2D and 3D domains. The algorithm is based on a fast ordered propagation distance transformation called occlusion points propagation geodesic distance transformation (OPPGDT) which is robust and linear in the domain size, and has higher accuracy than other geodesic distance transformations published before. Our approach has proved to have a computational complexity of order O(k.m) with m the domain size and k the order of the diagram. Voronoi diagrams have been extensively used in many areas and we show here that Voronoi diagrams computed in non convex domains, are extremely useful for the segmentation of medical images. We validated our algorithm with a set of 2D and 3D synthetic non convex domains, and with the segmentation of a medical dataset showing its robustness and performance.