Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
    
What have you tried? –  Raphael Nov 19 '12 at 18:21
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.