# Algorithm to find the vertices of the equidistant lines between N closed polygonal lines

I have a set $\{C_1, C_2, \ldots, C_N\}$ of $N$ nonintersecting closed piecewise linear curves on the Euclidean plane. For every point $x \in \mathbb{R}^2$ we say it belongs to a territory serviced by $C_i$ if $C_i$ is closest curve to $x$.

The boundaries of territories serviced by the $C_i$'s are clearly polygonal lines themselves (???). I am looking for the algorithm to find the vertices of each boundary.

I assume a "closed polygonal line" is a line segment. If so, the boundaries of the "territories serviced" are not polygonal, but rather contain parabolic arcs as well:

Search for the Voronoi diagram of line segments, and you will find, e.g., Meera Sitharam's lecture notes, (PDF download), which include the above image.
After the OP clarified that "closed piecewise linear curve" means "polygon," the situation is still pretty much the same:

(Image from Boost Voronoi Library.)

• I mean nonintersecting piecewise linear curves. But I guess the equidistant line is still not polygonal – vkrouglov May 22 '15 at 12:31
• I added an image of the Voronoi diagram of polygons. – Joseph O'Rourke May 22 '15 at 12:41