The Voronoi diagram is a well-known data structure that helps solve various proximity problems. We have several nice algorithms that build this diagram for $n$ point in optimal time $O(n\log n)$.

I am interested to solve this problem for a set of simple, disjoint polygons and I am collecting information about known solutions. Actually, what matters to me is to know for every polygon which other polygon shares an edge of the diagram with it, which is a quasi-equivalent problem (I mean that the graph structure is enough, I don't need the exact geometry).

I have heard of the compact Voronoi diagrams and the are certainly an option. I am also interested in the Voronoi diagram of the convex hulls of these polygons, which might be easier to construct, but in this case it is no more guaranteed that they are disjoint.

My polygons have a few dozens vertices and there are a few dozens of them. Approximate solutions are allowed. Speed and ease of implementation are more important.

I would welcome any information about these problems and their algorithmic resolution.

  • $\begingroup$ I don't understand what problem you're trying to solve. Given a set of points you can compute a Voronoi diagram. What do you mean by "solve this problem for a set of simple, disjoint polygons"? $\endgroup$ – D.W. Nov 9 '17 at 2:35
  • $\begingroup$ @D.W.: replace points by polygons. Like you can replace points by line segments, disks or other shapes. $\endgroup$ – Yves Daoust Nov 9 '17 at 8:55
  • $\begingroup$ Perhaps it would help to add the definition of the Voronoi diagram of polygons. I am familiar with the definition of a Voronoi diagram of a set of points, but I've never seen a definition for the Voronoi diagram of a set of polygons. Maybe this is something that every computational geometry expert will already be familiar with; if so, you can ignore my feedback. $\endgroup$ – D.W. Nov 9 '17 at 17:27
  • $\begingroup$ @D.W.: the Voronoi diagram is defined the same way for any shape: a Voronoi cell is the set of points closer to a given shape than to any other. This is indeed well-known in CG. Thanks for the interest. $\endgroup$ – Yves Daoust Nov 9 '17 at 17:32
  • $\begingroup$ If I'm not mistaken, the cell for a polygon is the union of the cells for its edges, if you have an algorithm for segments, there is thus a trivial one for polygons. Reciprocally, a segment is a degenerate polygon. If there was a better algorithm for polygon, you could use it for segments. If you have special algorithms for polygons, it looks to me that they are interesting only for special cases when compared to segment one. Do you have collected some? $\endgroup$ – AProgrammer Nov 10 '17 at 10:40

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.