Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to draw a Voronoi diagram with 9 sites and with

  1. no vertex,
  2. 1 vertex,
  3. 4 vertices, and
  4. 7 vertices.

How do I approach this question. The one with no vertex is easy, it can be done by collinear points. What about the others.

A figure for each would be appreciated.

share|cite|improve this question
up vote 4 down vote accepted

Conceptually, it is maybe easier to construct a Delaunay triangulation tessalation. The DT is the dual to the Voronoi diagramm, so you want to limit the number of faces to $0,1,4,7$. This can be achieved by placing some of the vertices of the DT on a circle, or by picking the right number of vertices on the convex hull.

Here is a picture for the 4 vertex case (black DT, red Voronoi diagramm). Play around to get the solutions of 2. and 4. (You already solved 1.)

enter image description here

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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