We present an original algorithm to construct Voronoi tessellations on surfaces from a set of depth maps. Based on a local graphbased structure, where each local graph spans one depth map, our algorithm is able to compute ...