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.

  • $\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$ Dec 9, 2019 at 20:59
  • $\begingroup$ Here is an additional link link.springer.com/chapter/10.1007%2FBFb0049411 $\endgroup$ Dec 9, 2019 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, 2019 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$ Dec 10, 2019 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, 2019 at 13:43

2 Answers 2


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

          enter image description here
          Image from GIS.

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.

  • 1
    $\begingroup$ Maybe it is worth to say that this diagram is made of line segments and parabolic arcs. $\endgroup$
    – user16034
    Dec 10, 2019 at 16:06

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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