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

<p>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.</p>

<p>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 <a href="http://link.springer.com/article/10.1007%2FBF01553882" rel="nofollow">paper</a> 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.</p>

<p><strong>Edit:</strong> 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$.</p>

CC BY-SA 3.0
2016-01-21T11:45:30.537Z
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?
Peter Taylor
CC BY-SA 3.0
2016-01-22T01:29:44.497Z
The holes are the obstacles, and the polygon with holes is the free space, I assume.
David Eppstein
CC BY-SA 3.0
2016-01-22T06:10:09.720Z
@DavidEppstein is correct.
Dibyayan
CC BY-SA 3.0
2016-01-23T04:41:41.530Z
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 http://eurogiga.inf.fu-berlin.de/w/pub/EuroGIGA/EuroGIGAFinalConference/geodesic-and-abstract-Voronoi-diagrams-Bonn_liu.pdf). I would contact the authors to see if they can solve your problem...
Sariel Har-Peled
CC BY-SA 3.0
2016-01-23T04:44:59.827Z
...not only the slides are very nice, but they also explicitly speak about geodesic Voronoi diagram. So maybe they already solved your problem.
Sariel Har-Peled
CC BY-SA 3.0
2016-09-05T08:53:17.737Z
@Dibyayan Check out http://dccg.upc.edu/people/vera/wp-content/uploads/2014/11/GA2014-DelaunayWithConstrainsDelaunay3D-Marc-Comino.pdf
kassak
<ds.algorithms><computational-geometry><polynomial-time><voronoi>
Voronoi diagram in presence of polygonal obstacle
Dibyayan
# Voronoi diagram in presence of polygonal obstacle

(Asked by: username_0 on 2016-01-21)

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](http://link.springer.com/article/10.1007%2FBF01553882) 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$.

**Tags:** ds.algorithms, computational-geometry, polynomial-time, voronoi
> **Comments:**
> **username_1**: 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?  
> **username_2**: The holes are the obstacles, and the polygon with holes is the free space, I assume.  
> **username_0**: @DavidEppstein is correct.  
> **username_3**: 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 http://eurogiga.inf.fu-berlin.de/w/pub/EuroGIGA/EuroGIGAFinalConference/geodesic-and-abstract-Voronoi-diagrams-Bonn_liu.pdf). I would contact the authors to see if they can solve your problem...  
> **username_3**: ...not only the slides are very nice, but they also explicitly speak about geodesic Voronoi diagram. So maybe they already solved your problem.  
> **username_4**: @Dibyayan Check out http://dccg.upc.edu/people/vera/wp-content/uploads/2014/11/GA2014-DelaunayWithConstrainsDelaunay3D-Marc-Comino.pdf  

---

## 0 answers

