Suppose there is a set of convex polygons ($\mathbb{P}$) on the plane. For each convex polygon $P_i$ there is one "facility" $f_i$ placed on the boundary of $P_i$.

The distance between a point $p \in \mathbb{R}^2\setminus \mathbb{P}$ and a facility $f_i$ is the distance of the shortest path between $p$ and $f_i$ avoiding interiors of the convex polygons.

My question is: Is there a known algorithm to compute the voronoi diagram ($\mathbb{V}$) in such settings ? I found something similar in Aronov's paper which deals with geodesic voronoi diagrams inside a simple polygon. Since, the paper does not considers holes inside the polygon it does not solve my problem.

Edit: The problem I stated can also be formulated as follows: Consider a large rectangle ($R$) containing $\mathbb{P}$ as convex holes inside it. The point sites are placed on the boundary of the holes. Now the geodesic voronoi diagram would be same as $\mathbb{V}$ bounded by $R$.

  • $\begingroup$ The question talks about convex polygons and polygons with holes inside them, but no polygon with a hole in can be convex. Could you clarify? $\endgroup$ Jan 21, 2016 at 11:45
  • $\begingroup$ The holes are the obstacles, and the polygon with holes is the free space, I assume. $\endgroup$ Jan 22, 2016 at 1:29
  • $\begingroup$ @DavidEppstein is correct. $\endgroup$
    – Dibyayan
    Jan 22, 2016 at 6:10
  • 1
    $\begingroup$ Yes and no. I doubt if anybody worked on this problem, but you should be able to use the known algorithms for Abstract Voronoi diagrams in this case. There is some recent work on the topic (see for example, what google found eurogiga.inf.fu-berlin.de/w/pub/EuroGIGA/…). I would contact the authors to see if they can solve your problem... $\endgroup$ Jan 23, 2016 at 4:41
  • 1
    $\begingroup$ ...not only the slides are very nice, but they also explicitly speak about geodesic Voronoi diagram. So maybe they already solved your problem. $\endgroup$ Jan 23, 2016 at 4:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.