If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Bonus Challenge

This article gives a step-by-step guide to how the boundary lines in a Voronoi diagram can be calculated.

The geometry of Voronoi partitions

A Voronoi partition is made by taking a set of sites spread on the screen and drawing boundaries between the sites, in such a way that each boundary is exactly halfway between the sites on either side of it.

Dividing two sites

Let's start with two sites, A and B. Every point on the line that divides them, is an equal distance from A and from B. What other properties does this line have?
Two sites and a boundary
The first thing we can do is to draw a line segment from A to B. Since all the points on the boundary are an equal distance from A and from B, the boundary will cross start overline, A, B, end overline at the midpoint, M.
You can learn more about midpoints here.
Line AB with midpoint marked M.
Now we can pick another point on the boundary, P and make two triangles: triangle, A, M, P and triangle, B, M, P.
Boundary with point P marked
Point P is on the boundary so we know that start overline, A, P, end overline, equals, start overline, B, P, end overline.
We also know that start overline, A, M, end overline, equals, start overline, B, M, end overline and that both triangles share side start overline, M, P, end overline.
Since both triangles share three side lengths, they are similar triangles. You can learn more about similar triangles here.
Since triangle, A, M, P and triangle, B, M, P are similar we know that angle, A, M, P, equals, angle, B, M, P. Since both angles lie on a straight line (line A, B), we know that angle, A, M, P, plus, angle, B, M, P, equals, 180, degrees. So both angles must be 90, degrees.
Therefore, the boundary between A and B is the perpendicular bisector of the line A, B. You can learn more about perpendicular bisectors here.

Dividing three sites

So we know the boundary between two sites is a perpendicular bisector of the line joining those sites. How can we use this information to find the Voronoi partition of three sites? First let's start by drawing lines between the sites.
Triangle ABC
Next we find the midpoints of the edges and draw the perpendicular bisector for each edge.
Triangle with perpendicular bisectors for each edge.
Notice that the three perpendicular bisectors meet at a point, V. Since each perpendicular bisector is an equal distance from two sites and V lies on all three of them, V must be an equal distance from all three site. V is therefore a vertex in our Voronoi partition. We can draw our final boundaries by starting from this vertex and continuing through each of the midpoints.
Perpendicular bisectors meeting at point V
The final Voronoi partition

Questions

  1. What is the term for point V in relation to triangle, A, B, C?
  2. Under what circumstances will the perpendicular bisectors not intersect each other?

The algebra of Voronoi partitions

Now we've seen some of the geometry of a simple Voronoi partition, let's use algebra to calculate the coordinates for a vertex in a Voronoi partition.
Say we have three sites, A, B, and C with coordinates:
A, equals, left parenthesis, 30, comma, 60, right parenthesis
B, equals, left parenthesis, 90, comma, 80, right parenthesis
C, equals, left parenthesis, 150, comma, 20, right parenthesis
Let's first calculate the equation for the perpendicular bisector of start overline, A, B, end overline. We know this line will pass through the midpoint of start overline, A, B, end overline and have the negative inverse gradient of start overline, A, B, end overline.
Learn how to calculate the equation of a perpendicular line here.
What is the midpoint of start overline, A, B, end overline? left parenthesis
  • Your answer should be
  • an integer, like 6
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4
  • a mixed number, like 1, space, 3, slash, 4
  • an exact decimal, like 0, point, 75
  • a multiple of pi, like 12, space, start text, p, i, end text or 2, slash, 3, space, start text, p, i, end text
,
  • Your answer should be
  • an integer, like 6
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4
  • a mixed number, like 1, space, 3, slash, 4
  • an exact decimal, like 0, point, 75
  • a multiple of pi, like 12, space, start text, p, i, end text or 2, slash, 3, space, start text, p, i, end text
right parenthesis

What is the gradient of start overline, A, B, end overline?
  • Your answer should be
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4

What is the gradient of the perpendicular bisector of start overline, A, B, end overline?
  • Your answer should be
  • an integer, like 6
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4
  • a mixed number, like 1, space, 3, slash, 4
  • an exact decimal, like 0, point, 75
  • a multiple of pi, like 12, space, start text, p, i, end text or 2, slash, 3, space, start text, p, i, end text

What is the equation for the perpendicular bisector of start overline, A, B, end overline?
y, equals
  • Your answer should be
  • an integer, like 6
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4
  • a mixed number, like 1, space, 3, slash, 4
  • an exact decimal, like 0, point, 75
  • a multiple of pi, like 12, space, start text, p, i, end text or 2, slash, 3, space, start text, p, i, end text
x, plus
  • Your answer should be
  • an integer, like 6
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4
  • a mixed number, like 1, space, 3, slash, 4
  • an exact decimal, like 0, point, 75
  • a multiple of pi, like 12, space, start text, p, i, end text or 2, slash, 3, space, start text, p, i, end text

Now we have the equation for the perpendicular bisector of start overline, A, B, end overline, we can use the same approach to calculate the perpendicular bisector of start overline, B, C, end overline.
What is the equation of the perpendicular bisector of start overline, B, C, end overline?
y, equals
  • Your answer should be
  • an integer, like 6
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4
  • a mixed number, like 1, space, 3, slash, 4
  • an exact decimal, like 0, point, 75
  • a multiple of pi, like 12, space, start text, p, i, end text or 2, slash, 3, space, start text, p, i, end text
x, plus
  • Your answer should be
  • an integer, like 6
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4
  • a mixed number, like 1, space, 3, slash, 4
  • an exact decimal, like 0, point, 75
  • a multiple of pi, like 12, space, start text, p, i, end text or 2, slash, 3, space, start text, p, i, end text

Now we have the equations for two perpendicular bisectors we can calculate where they intersect. If we use m, start subscript, 1, end subscript and b, start subscript, 1, end subscript to represent the gradient and y-intersect the first perpendicular bisector and m, start subscript, 2, end subscript and b, start subscript, 2, end subscript to represent the gradient and y-intersect the second perpendicular bisector, we have:
y=m1x+b1y=m2x+b2\qquad \begin{aligned} y &= m_1 x + b_1 \\ y &= m_2 x + b_2 \end{aligned}
So:
m1x+b1=m2x+b2m1xm2x=b2b1(m1m2)x=b2b1x=b2b1m1m2\qquad \begin{aligned} m_1 x + b_1 &= m_2 x + b_2 \\ \\ m_1 x - m_2 x &= b_2 - b_1 \\ \\ (m_1 - m_2)x &= b_2 - b_1 \\ \\ x &=\dfrac{b_2 - b_1}{m_1 - m_2} \end{aligned}
Plug the values for the gradients and y-intersects into the equation to find the x coordinate of the intersection point. Then plug the value for x into one of the equations for a perpendicular bisector to find the y coordinate.
Where do the perpendicular bisectors intersect? left parenthesis
  • Your answer should be
  • an integer, like 6
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4
  • a mixed number, like 1, space, 3, slash, 4
  • an exact decimal, like 0, point, 75
  • a multiple of pi, like 12, space, start text, p, i, end text or 2, slash, 3, space, start text, p, i, end text
,
  • Your answer should be
  • an integer, like 6
  • a simplified proper fraction, like 3, slash, 5
  • a simplified improper fraction, like 7, slash, 4
  • a mixed number, like 1, space, 3, slash, 4
  • an exact decimal, like 0, point, 75
  • a multiple of pi, like 12, space, start text, p, i, end text or 2, slash, 3, space, start text, p, i, end text
right parenthesis

Now imagine calculating this for hundreds of sites. This is why we use computers!

Want to join the conversation?

  • winston baby style avatar for user Jordan
    Hi there! I really love all the Pixar lessons and am so happy you guys added the "Patterns" program on! This course was personally my favorite, and I would love to do more of this kind of stuff. I was wondering though, does this certain category have a certain name? I also wrote in earlier this year about character modeling and I was wondering if there is a field that ties both of these categories together? Also it would be awesome if you could attach a list of field names that relate to these subjects. Thank you so much! I appreciate all the time and effort you put into these lessons!
    (64 votes)
    Default Khan Academy avatar avatar for user
    • leafers ultimate style avatar for user Bryan Ray
      The practice of creating images using mathematical formulae and algorithms is called "computational imaging." It is a pretty narrow application of more general math, geometry, and graphics programming skills.

      Synthetic imagery and patterns are very commonly used in character modeling—adding displacement detail and, of course, texture to a model. If you experiment with the program ZBrush, you can see how patterns like Perlin noise can be added directly to a character mesh. I think you can do it in Blender's sculpt mode, too, but don't quote me on that.

      If you're looking for educational programs to pursue, look for schools that offer things like visual effects, animation, video game design, computer graphics, interactive media, virtual reality, and similar things. You could also come at it through the research side by studying mathematics, computer science, or image processing.

      If you'd like to learn a lot more about modeling, I recommend the book [Digital] Modeling by William Vaughan from New Riders. ISBN-13: 978-0321700896

      In fact, the entire [Digital] series is pretty good. [Digital] Texturing and Painting by Owen Demers (ISBN-13: 978-0735709188) has some nice stuff in it about pattern creation and applying them to a character.
      (23 votes)
  • spunky sam blue style avatar for user Niramay Gogate
    Will we be using readymade software to construct veronoi partitions or we need to write a program for it?
    (12 votes)
    Default Khan Academy avatar avatar for user
  • female robot ada style avatar for user Anuscke
    Hi guys! what is a gradient in the second question of The Algebra Of Voronoi Partition? I don't quite understand the question.
    thanxs
    (5 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Olivia Cassar
    How does this help you with patterns in real life?
    (6 votes)
    Default Khan Academy avatar avatar for user
    • female robot ada style avatar for user Andromeda
      Well, if you want to be an animator or the like when you grow up, it would help you to get a basic knowledge of the tools animators use in their work. That's the cool thing about these courses--they give you a sense of what different jobs/projects would be like, and let you try things out yourself. I hope that answers your question!
      (3 votes)
  • marcimus pink style avatar for user Shafia Azim
    Anyone wanna say HI (or need any help)(LOL I idk what to do)!!
    (4 votes)
    Default Khan Academy avatar avatar for user
  • mr pants pink style avatar for user mmorales0362
    how do we do this and what grade is this?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • male robot donald style avatar for user Enzo McElhaney
    This bonus is VERY hard I got all of them wrong sorry :[ ;[ cry..
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user arnoldgitia
    Are those all we need to know?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • duskpin ultimate style avatar for user Dana
    I'm on the "What is the equation for the perpendicular bisector of AB?" and frankly I'm not sure why my answer is not correct. They want m to be the gradient of AB, not the perpendicular bisector, right? So then m = 1/3. I did 60 = (1/3)(30) + b and got b = 50. But the answer is wrong. :( Could someone clarify this, please?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • male robot hal style avatar for user Boon1005
    var saveData = {
    edgeWidth: 98,
    jitter: 50,
    extrude: 10,
    skinColor: -11582429,
    scaleColor1: -4938931,
    scaleColor2: -11503476,
    skinAmplitudes: [0,0,0],
    scaleAmplitudes: [0,0,0],
    sites: [[145.939,498.243],[306.915,495.932],[-63.136,495.183],[79.896,479.111],[401.756,467.633],[23.797,459.774],[219.542,458.266],[452.679,457.042],[355.548,448.305],[145.873,443.297],[-75.677,430.6],[262.304,426.482],[59.483,424.111],[-9.662,417.404],[106.166,402.259],[417.288,394.01],[477.18,390.161],[318.157,385.962],[29.253,378.857],[198.932,370.622],[147.264,365.816],[367.106,365.018],[-28.001,362.074],[459.348,342.386],[-84.528,339.497],[151,336],[184,335],[267.634,330.264],[128.529,313.306],[228,311],[70.904,310.494],[364.505,309.573],[186.812,301.577],[16.096,299.534],[303.241,291.077],[-64.176,289.317],[127,289],[267,283],[432.781,263.325],[483.547,260.64],[239.683,255.877],[118.104,250.14],[65.896,249.123],[167.91,245.259],[258,239],[329.228,236.652],[379.975,235.89],[124,224],[-13.928,217.474],[490.167,205.445],[265.464,201.037],[199,196],[33.048,195.763],[138,194],[116,193],[164.5,187.596],[239,184],[344.247,174.798],[114.551,171.571],[442.833,170.625],[-64.726,167.623],[220.404,166.731],[53.168,148.434],[115,143],[401.209,140.471],[225,133],[309.888,131.798],[171.19,131.788],[90,130],[-7.047,129.462],[494.535,116.778],[263.524,112.745],[-57.682,107.96],[124.334,107.313],[208.6,98.137],[445.441,95.467],[67.069,90.292],[376.515,90.239],[187,75],[113,72],[292.501,71.871],[16.563,71.817],[158.462,69.219],[237.991,48.27],[85.204,41.388],[-36.941,40.876],[440.924,34.536],[494.54,24.955],[327.362,18.121],[150.563,-0.134],[274.609,-3.58],[203.11,-4.027],[372.695,-6.224],[4.424,-10.262],[467.277,-18.473],[329.895,-34.524],[96.012,-43.1],[-38.056,-47.609],[190.599,-61.365],[419.141,-63.567],[263.144,-70.134],[49.338,-77.015],]
    };

    Paste the code above into:
    https://www.khanacademy.org/pixar/a/5620766808
    (1 vote)
    Default Khan Academy avatar avatar for user