in this video we look at Voronoi diagrams which is part of the AI course SL and HL under topic 3 geometry and trigonometry now there are five key concepts that I want to go through but I'm going to start with some terminology here so from here on in I'm going to use these words that I'm about to introduce and I recommend that you do also okay in a Voronoi diagram which is this diagram that you can see here there are coordinates so coordinates a B C and D and we would call them coordinates when we're talking about coordinate geometry however when we're talking about Voronoi diagrams we actually call these sites now the sites are separated by these lines here and we call these lines edges the edges creates some region so that for example this top left region here and then the top right region here and we call these we either call the regions or some textbooks call themselves so two words here for that for that for this particular space which is created by the edges now finally where the edges intersect so for example P and Q we call these intersections so for new words here and this is the terminology when talking about a Voronoi diagram so in this example diagram here we have four sites we have four regions we have a series of edges and we have two intersections okay let's now talk about what our VAR annoy diagrams now a Voronoi diagram is kind of like a map so picture it like a map of an area and you're looking to maybe go in a certain direction now the map here is separated by these edges and what's important about this and it's kind of the whole purpose of a Voronoi diagram is that any particular location within a region let's focus here on the region containing site c any location within that region so it could be a location here it could be a location here it could be a location here anywhere within this region any of these locations our closest to sightsee so for example this particular Voronoi diagram and I took out of the question back section shows the location of four Pizza Shops Peter shop a B C and D now if you're hungry one day and you're in the city and you want to find the closest pizza shop you want to know well which one is closest to me well if you happen to have a Voronoi diagram and you realize that you were say in this location here you could say well I am within the region containing site D so therefore I am closest to Sun to site D or the pizza shop located at site D if you happen to be standing on an edge so for example right here you're actually equally close to the pizza shop located at site a or site D so that's what a Voronoi diagram is the whole point is which region are we in or which region is a location in and that can tell you the site that you are closest to okay let's now talk about key concept rehouse Orono diagram is constructed they're constructed by a series of perpendicular bisectors so for example if I look at regions the region containing site D and the region containing site C it's separated by this vertical edge here this line here now this line here happens to be the perpendicular bisector between coordinate D and coordinates C now in this video I won't go through how to actually find the equation of this line there is a key concept video in topic 2 titled perpendicular bisectors which goes through exactly that concept but the important point here is all Voronoi diagrams are are just a series of perpendicular bisectors so for example this horizontal line here is the perpendicular bisector between coordinate a and coordinate D now I'm using the word coordinate they're not sight because when we go to create this perpendicular bisector we need to identify the coordinates a and D this line here is it bisects it so it's halfway between a and D and it's also perpendicular to the line segment that if we would if we were to create a line between coordinate a and D this perpendicular bisector would set perpendicular to that line segment it would create a right angle here but for more information about perpendicular bisectors I recommend going than watching that key concept video over at topic 2 but just to recap Voronoi diagrams are just a whole series of perpendicular bisectors that's all they are now it obviously does take a long time to construct one in an IRB exam you won't be expected to actually make one a full Voronoi diagram because that would just take too long a typical exam question might say look there's one missing edge in in a particular Voronoi diagram go ahead and find the equation of the line that will complete that for anoi diagram that's what a sort of a medium level Voronoi diagram IB exam question will ask and easier one might just say if I'm located at coordinate so let's say 6 & 4 which site are my closest to so that's a pretty simple question there okay let's now move on to key concept for here this concept called nearest neighbor interpolation and let's go back to this verano diagram here which I mentioned shows the location of for pizza shops a B C and D now let's pretend that you want to open a new pizza restaurant and it is located at coordinates six and five so this location here now we've already identified that because it is within the region containing site B it is closest to the pizza restaurant at B now what if you were to try to determine well how many pizzas a week do I think my restaurant will will be able to sell you want to try to do some budgeting and try to try to determine whether your pizza shop will be profitable and you're trying to estimate well how many pizzas will my shop sell well using this concept nearest neighbor interpolation we can actually estimate the average number of pizzas sold safe per week by actually going to the closest site so pizza restaurant B and just using the average of pizza shop B that's as simple as it is so for example this table here given in the question from the question Bank it says that the pizza shop located at site B sold what an average of one thousand seven hundred and fifty two Peters per week so therefore using nearest neighbor interpolation we can estimate that the new pizza shop located here because it's closest to B so it's it's its nearest neighbor is B we can say we well we're going to estimate that it will also sell 1750 to sir yeah one thousand seven fifty two pizzas per week okay let's no talk about the final key concept this is called the largest empty circle problem and it's otherwise known as the toxic waste dump problem now what it is the whole sort of point about topic five I'll just firstly talk about the largest empty circle and then I'll give it some context when I'm talking about a toxic waste on the question that I posed to you is what is the largest possible circle that I could draw on this Voronoi diagram and I'll use a different color I'll use blue what is the largest possible circle that I could draw on this diagram that does not contain a site within it so for example this small one here that's pretty good that doesn't contain a site within it what about if I went a little bit bigger well that circle that I just drew there now contains site C okay so what about if I if I drew a big one say here with a center roughly about here that's a pretty big circle and it doesn't contain sites a B C and D it can contain an intersection of just it we just can't let it contain a site now you may be thinking okay what's the point of this and this comes into there's usually sort of two types of questions here the first is where could we position a toxic waste dump which is the furthest away from any of the sites which is usually like a town or a or a cluster of houses now of course you want to toxic waste up quite a long way away from that so you want to be our to position at toxic-waste on which will be at the center of this circle that is a long way away from any of the sites so that's one type of largest empty circle problem the other is actually like this example here would be where can I position a new pizza restaurant such that it is as far away from any other restaurant as possible now the answer to this question is this largest empty circle it will all the center of this circle will always occur at one of the intersections and then you need to determine which intersection should it see that and the way that you do that is to actually test how far is intersection from its nearest neighbor but I won't go into all the details in this video because that will take a bit too long there are quite a few of these questions located in the question Bank but the key point here the large the center of the largest empty circle will always occur at one of the intersections okay that's a quick overview into Voronoi diagrams I recommend practicing some of these questions they're actually quite enjoyable questions to go through they're always very contextual they're usually quite interesting questions and yes I recommend practicing some of these questions over in the question Bank section