2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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:

         VoronoiSegments
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:
         VoronoiPolygons
         (Image from Boost Voronoi Library.)

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .