Voronoi Diagrams

Question 1

What’s a Voronoi diagram?

Answer 1

A diagram that breaks up a space into regions closest to a set of points.

Question 2

What are the steps to draw a Voronoi Diagram?

Answer 2

1. Choose a site to start with.
   
   • Draw the perpendicular bisector between this site and each of it’s neighbors neighbor.
   • Starting at the edge of the whole diagram, trace along your lines to outline the boundaries of the cell.
   • Erase the extra part of the lines that you don’t need for the boundary of the cell.
2. Keep repeating this process for each site.

Question 3

How do you find the line that separates two sites?

Answer 3

It’s a perpendicular bisector.

1. Find the midpoint of the two given points.
2. Find the gradient between the two given points.
3. Identify the gradient of the perpendicular bisector. (The negative reciprocal of what you found in step 2.)
4. Substitute the gradient info into formula for a straight line.
5. Next substitute your midpoint in for x and y and solve for b.
6. Write the equation of the line in the form , but use your values for m and b.

Question 4

What is the significance of a cell?

Answer 4

Every point in the cell is closer to that site than any other site.

Question 5

How would you find the coordinates of A?

Answer 5

1. Find the equation of the line that connects A and B.
2. Find the intersection of this new line and the one given. (This will be the midpoint between A and B.)
3. Use the x-coordinates from B and M in the midpoint formula to find the x-coordinate of A.
4. Use the y-coordinates from B and M in the midpoint formula to find the y-coordinate of A.

Question 6

If you want to add another point to a Voronoi diagram that is “the furthest from all existing sites”, where should it go?

Answer 6

It should go at the vertex between the existing sites.