Voronoi diagrams with barriers and on polyhedra for minimal path planning

Two generalizations of the Voronoi diagram in two dimensions (E-2) are presented in this paper. The first allows impenetrable barriers that the shortest path must go around. The barriers are straight line segments that may be combined into polygons and even mazes. Each region of the diagram delimits a set of points that have not only the same closest existing point, but have the same topology of shortest path. The edges of this diagram, which has linear complexity in the number of input points and barrier lines, may be hyperbolic sections as well as straight lines. The second construction considers the Voronoi diagram on the surface of a convex polyhedron, given a set of fixed source points on it. Each face is partitioned into regions, such that the shortest path to any goal point in a given region from the closest fixed source point travels over the same sequence of faces to the same closest point.