Voronoi Diagram for Intersecting Convex Polygons in the Plane

The traditional polygonal Voronoi diagram does not allow intersections among polygons and henceforth is hard to be applied to the fields of computer vision and ecology where polygons may intersect each other.In order to solve the problem of the nearest neighbor partitions under situations with polygon intersection,a novel Voronoi diagram for intersecting convex polygons is proposed.Firstly,the Voronoi diagram for intersecting convex polygons is defined.Then the unique regionalization feature of Voronoi edges is described,followed by the proof of the necessary and sufficient condition for its occurrence.Moreover,the relation between intersecting polygons and disjoint polygons is demonstrated.Finally,the generation algorithm of the polygonal Voronoi diagram is proposed and implemented.Experimental results show that the algorithm breaks through the constraint of having no intersecting polygons and effectively solves the problem of intersection in the polygonal Voronoi diagram,which provides the theoretic foundation for practical applications in the fields of computer vision and ecology.