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

How do you find the line that separates two sites?

Answer 2

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 3

What is the significance of a cell?

Answer 3

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

Question 4

How would you find the coordinates of A?

Answer 4

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 5

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

Answer 5

It should go at the vertex between the existing sites.

Question 6

What are the steps to find the equation between two sites?

Answer 6

1. Find the midpoint between the two sites.
2. Find the gradient connecting the sites
3. Take the negative reciprocal to get the gradient of your line (m)
4. Plug the x and y from your midpoint and the gradient into the y=mx+c formula to solve for c.
5. Write the equation as y=mx+c (but m and c need to be numbers).