7
$\begingroup$

I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays.

Similarly how can we draw the Voronoi diagram for the following: (a) A set of lines and points? (b) A set of disjoint line segments? (c) A set of line segments forming a convex polygon? (d) A set of circles (non intersecting and no circle contains another)?

For each of these sets of objects, how can we describe the shape of the boundary pieces that form the Voronoi diagram.

I believe that the distance between a point and another object is the smallest distance between the point and any point of the object.

Improve this question
$\endgroup$
  • $\begingroup$ I think in most of the cases, the Voronoi diagram can be very arbitrary and is not necessarily made out of straight lines. Note that a parabola defines per definition the Voronoi diagram of a line and a point. Also non-rational numbers might be included $\endgroup$ – narek Bojikian Dec 9 '19 at 20:59
  • $\begingroup$ Here is an additional link link.springer.com/chapter/10.1007%2FBFb0049411 $\endgroup$ – narek Bojikian Dec 9 '19 at 20:59
  • 1
    $\begingroup$ For non intersecting disks however, the set of points at equal distance to two disks is still a line, so the Voronoi Diagram will have only straight edges. $\endgroup$ – Tassle Dec 9 '19 at 22:04
  • $\begingroup$ @Tassle, does this work also for non-intersecting disks of different radii? It does not seem trivial to me. A link would be very appreciated $\endgroup$ – narek Bojikian Dec 10 '19 at 3:20
  • $\begingroup$ I can't give a link because I spoke too fast and it doesn't work with different radii. My bad. $\endgroup$ – Tassle Dec 10 '19 at 13:43
3
$\begingroup$

The Voronoi diagram of disjoint segments (b) has been thoroughly studied.

          enter image description here
          Image from GIS.
See:

CGAL Manual, Chapter 43: 2D Segment Voronoi Diagrams. CGAL link.

For the Voronoi diagram of circles (d), see:

Jin, Li, Donguk Kim, Lisen Mu, Deok-Soo Kim, and Shi-Min Hu. "A sweepline algorithm for Euclidean Voronoi diagram of circles." Computer-Aided Design 38, no. 3 (2006): 260-272. Journal link.

Huber, Stefan. Computation of Voronoi diagrams of circular arcs and straight lines. Magisterarbeit, 2008.

To quote the latter: "Lemma 1.4. The bisector between two circles (...) consists of ellipses and hyperbolas." PDF download.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Maybe it is worth to say that this diagram is made of line segments and parabolic arcs. $\endgroup$ – Yves Daoust Dec 10 '19 at 16:06
3
$\begingroup$

The edges of a Voronoi diagram are the curves at equal distance from two geometric entities.

  • for two points, the mediatrix,

  • for two lines, the bissectrix,

  • for a line and a point, a parabola,

  • for two circles, a general conic.

The vertices are the intersections of two equidistant curves.

The diagram can also be seen as the set of crest lines of the distance map to the entities.

Improve this answer
$\endgroup$

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.