In this video, we're going to work the problem of finding
the closest point out of a set of points to some other given point.
We'll start by doing an instance of this problem by ourselves.
To do that, I've begun by drawing
a Cartesian coordinate grid and choosing a set S of points,
which you can see here,
another point P, which is one, negative one.
We're going to find the point in S that is closest to
P. The first thing I'm going to do is to draw my points on my Cartesian plane.
Now, I can begin working through this.
First, I need some domain knowledge.
I need the mathematical definition of the distance between two points,
which if you don't remember,
is the difference in the x values squared plus the difference in
the y values squared and then we take the square root of that.
So the way that I would do this is calculate the distance between P and two,
seven, and I would come up with 8.06.
Then, I would compute the distance between P and 10,
5 and come up with 10.82.
The first point was closer,
so I'm going to keep that.
This point is 7.07 away,
so I'm going to keep the new closest point so far.
This point is 7.81 away,
so eight, negative two is still closer.
This point is 5.66 away,
so we have a new closest point.
This point is 9.06 away,
so negative three, negative five is closer.
This point is 9.22 away,
so negative three, negative five is still closer.
And there are no more points to test, so negative three,
negative five is my answer to which point is closest to one, negative one.
If we visually inspect this picture,
that seems pretty reasonable.
It looks like the closest.
Now, I write down exactly what I just did.
I computed one squared plus eight squared,
took the square root and got about 8.06.
I computed the square root of nine squared plus six squared and got 10.82,
and I compared 10.82 to 8.06 and said 8.06 is smaller.
I computed the square root of seven squared plus negative one squared and got 7.07,
and I compared 7.07 to 8.06 and said 7.07 is smaller,
so this is a better choice.
Then I compared the square root of six squared plus negative five squared and got 7.81.
I compared 7.81 with 7.07 and got that 7.07 was smaller and so on and so on and so on.
And then when I got to the end,
I gave my answer as negative three, negative five.
These seem like reasonable steps,
but we actually glossed over
something that we did in the process of writing these steps down.
It is very important that we write our steps down
carefully because if we're missing steps,
we're going to miss them when we go to generalize and end up having a problem.
Here's an important clue.
Look at this step where we give an answer of negative three, negative five.
When we go to generalize,
we're going to ask, "Why did we use negative three, negative five?"
Then we're going to notice we don't see negative three,
negative five anywhere else.
The fact that our answer seemingly comes out of
nowhere indicates that we're missing something.
We did some step without consciously thinking about it and writing it down,
and we need to fix that before we go on.
We may notice this now,
we may notice it when we go to generalize,
in which case we need to come back and fix it.
Why was it that we picked negative three,
negative five as our answer here?
Reviewing our last steps,
the last remaining dotted line of length 5.66 is what we were keeping track of,
our best choice so far.
We started at point two, seven,
then we went around and updated it each time we found a shorter distance.
However, as we wrote our steps,
we never mentioned the point that went with the shortest distance so far.
We should go back and fix our steps to include that.
We start with a best choice of two, seven.
When we got to eight, negative two and decided 7.07 was smaller,
we updated our closest point to eight, negative two.
When we got to negative three,
negative five and found that 5.66 was smaller,
we updated our best choice to negative three, negative five.
Now, this answer at the end makes sense.
It is whatever our best choice was last.
Now we're ready to generalize,
which we'll do in the next video.
Andrew D. HiltonAssociate Professor of the Practice
Genevieve M. LippAdjunct Professor
Anne BracySenior Lecturer
