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.

Thanks, Vladimir


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

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.