Restrict Voronoï diagram to a polygon

Question

I managed to build the Voronoï diagram of n points using Fortune's algorithm.

This gives me a set of half-edges, some of which being infinite (no starting point and/or no end point).

I'd like to restrict this diagram to a specific polygon P, by creating new vertices at the intersections of the polygon and the inifinite half-edges and connecting them in order to close all cells of the diagram.

If P is convex, I think I can perform it in O(n log p) where p is the size of P, by finding the intersecting edge of P for each half-edge.

My questions are :

• Is there some way to do better in the case of a convex polygon ?
• Can we do something in the general case (any polygon, not convex)

Answer 1

Building the Voronoï diagram of $n$ points already takes time $O(n \log n)$. I assume that what you want to compute is the intersection of the Voronoï diagram with the polygon. One way to compute this in time $O((n+p+k) \log(n+p))$ (where $k$ is the number intersection points between the polygon and the Voronoï diagram) is to first compute the Voronoï diagram, and then compute the intersection with the polygon by any sufficiently fast algorithm (for example a sweepline algorithm using Bentley–Ottmann at its core).

For a general polygon, we have $k=O(np)$. For a convex polygon, we have $k=O(n)$, and you probably assume $p<n$, so $O((n+p+k) \log(n+p))=O(n\log n)$. This is worse than $O(n\log k)$, but only because we ignored the time $O(n \log n)$ required to build the Voronoï diagram.

(I know that making Bentley–Ottmann numerical robust is challenging, and most available robust implementation use "exact predicates" based on multi-precision arithmetic. But even if this answer might not be the most practical, it answers your questions with respect to computational complexity of the task at hand.)

Answer 2

I suggest using the method described in a recent paper I published: http://people.seas.harvard.edu/~nbonneel/vorpaline.pdf

The idea is simple, and is as follows :
You start with your polygon, and the goal is to cut it with the mediator planes defined by each seed using Sutherland-Hodgman polygon clipping algorithm. That can be efficiently done in parallel for each seed.

Given a set of $n$ points $\{P_i\}$, let's say you want to compute the Voronoi cell of the seed $P_k$. First, you sort all the $\{P_i\}$ by increasing distance to $P_k$ (for the current seed, this is $O(\log(n))$ using a kd-tree ). You clip your polygon by the mediator plane of the segment $[P_k, P_i]$ and store the distance $D$ from $P_k$ to the furthest intersection. When for a given $i$, the distance between $P_k$ and $P_i$ is greater than $2\,D$, you can stop and this result in the Voronoi cell restricted to your polygon (further points will not contribute to any intersection).

The overall algorithm is $O(n\log(n))$ and can be done in parallel for each seed : $O(n\log(n))$ is required to build the kd-tree, then for each seed there is a $O(\log(n))$ nearest neighbor query, and each query result in $O(1)$ Sutherland-Hodgman polygon clippings.