4
$\begingroup$

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$.

$\endgroup$
  • $\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$ – Peter Taylor Jan 21 '16 at 11:45
  • $\begingroup$ The holes are the obstacles, and the polygon with holes is the free space, I assume. $\endgroup$ – David Eppstein Jan 22 '16 at 1:29
  • $\begingroup$ @DavidEppstein is correct. $\endgroup$ – Dibyayan Jan 22 '16 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$ – Sariel Har-Peled Jan 23 '16 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$ – Sariel Har-Peled Jan 23 '16 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.