Find point closest to three lines

[takbq2]

1. I would actually rather not give the equations. I'm not looking for someone to do this for me I just want a very quick reference on where to start or how to structure the solution and I can get it on my own.
2. I think Least Squares? This is why I haven't started it because I'm not sure the relevant equations.

 

[phinds]

Are the 3 lines in 3D space or 2D space? I don't have a solution for you, but I do know that for there to BE a solution, this has to be specified.

 

[takbq2]

whoops, 2D. y = 2-x, y=3-2x, and y = -6+4x

 

[hotvette]

I think Least Squares? This is why I haven't started it because I'm not sure the relevant equations

The fundamental approach is the same as least squares, though the term usually refers to curve fitting situations where the number of data points is more than the number of unknown function parameters.

The key here is to recognize this as a function minimization problem and establish (1) the correct function to be minimized and (2) the unknowns. After that, it's a straightforward multi-variable minimization problem.

 

[takbq2]

My intuition tells me that I need to do something like pick (guess) a point pretty close to all three (just looking at them after plotting all three with arbitrary x's) then use the distance formula for the distance between a point and a line, and minimize d. That would get me minimized to one line, but it would put me on the line unless I use the other lines as constraints. Hmm.. lagrange multipliers? This is supposed to be an easy question and I am stupidly missing something big.

By the way, thanks for your input hotvette.

 

[phinds]

I would start by finding the equation of the line that bisects the angle between two of the other lines and that is the bisector that has the least distance to the 3rd line. Then find a point on the bisector line and get the distance to all three lines and minimize that quantity.

This approach sounds baggy as hell to me and would result in very messy algebra but is the only think I can think of that would get you there and I'm not even sure it would get the absolute min since I can't think why the min would have to be on a bisector.

Hovetts' statement that it would then be a "straightforward multi-variable minimization problem" seems to me to gloss over some REALLY ugly algebra.

I agree w/ you that it just seems like there should be some simple (at LEAST conceptually simple) and elegant approach but I don't see what it is.

 

[hotvette]

How ugly things get depends on whether the answer can be numeric only or needs to be an algebraic expression. The numeric approach is straightforward:

1. Write a single expression for the qty to be minimized. In this case, the sum of distances between an unknown point x*, y* and the three lines. Hint: it is a LOT easier to deal with distance squared rather than distance.

2. There are 5 unknowns: the coordinates of the point x*, y* and x-values on the three lines that represent the location of the shortest distance (the y-values come from the equations of the lines). Note: we all know the shortest distance to each line happens to be normal to the line, but that can be completely ignored when treating this as a simple function minimization problem.

3. Set partial derivatives of the fuction (i.e. sum of squared distances) with respect to each of the 5 unknowns equal to zero

4. Result is a 5 x 5 linear matrix equation that can be solved numerically for the 5 unknowns. The 5 equations could, in fact, be solved algebraically, but that would be quite ugly.

An algebraic approach can be as follows:

1. Assume a fixed point x*, y* and use calculus to find the shortest distance to one of the lines. Result is an algebraic expression for the x-value on the line in terms of x*, y* and known line parameters. Same result could be obtained using geometry.

2. Repeat step 1. for the remaining 2 lines. This can be done by inspection.

3. Write a single expression for the qty to be minimized. In this case, there will only be two unknowns (x*, y*). Setting partial derivatives wrt to the unknowns equal to zero results in two equations and two unknowns that can be readily solved algebraically. Ugly for sure.

This is supposed to be an easy question and I am stupidly missing something big.

If this is suppose to be an easy question, then I'm missing something also. Lagrange multipliers? Hmmm...maybe.

 

[takbq2]

Thanks a lot, phinds and hotvette. I'll have at it for awhile.

 

[hotvette]

Ah, I found an elegant trick. The key is a concise expression for the distance from a point to a line:

http://www.intmath.com/plane-analytic-geometry/perpendicular-distance-point-line.php

Once you have that, the expression for sum of squared distances from the point to the 3 lines isn't so ugly. Note the comment part way down in the link:

We now do a trick to make things easier for ourselves (the algebra is really horrible otherwise). We construct a line parallel to DE through (m, n)...

 

[takbq2]

I'm def. going to do it numerically. I just need to get the matrix. I see what you are saying how there are 5 unknowns, but in my term to be minimized I only have two, (a,b), the unknown point. So I can't take partials w/r/t each of the 5 variables. Did I do something wrong?

The distance between a point and a line in y = mx + b form (which mine are) is

| y₀ - mx₀ - b| / sqrt(m² + 1)

where x₀ and y₀ is the point I'm looking for.

But then you square this formula for simplicity because finding the smallest sum of the squares of the distances will minimize just as well as finding the smallest sum of the distances.

so then you just get the same formula with the numerator in parentheses and squared instead and the sqrt gone from the denominator.

Apply this formula to each of my three lines and sum:

d(line one) + d(line 2) + d(line 3)

but it does not contain the other three unknowns because the d formula only uses the point and slope of the other lines which are known...

so how do I get my 5x5 matrix :(

 

[takbq2]

whoa, we posted same time -- it looks like that is what I've done.. but now what about my matrix? I have the expression to be minimized but it only contains the unknown point unknowns a and b.

 

[takbq2]

In other words, how do I minimize:

(x₀+y₀-2)²
2

+

(2x₀+y₀-3)²
5

+

(-4x₀+y₀+6)²
17

 

[hotvette]

In other words, how do I minimize:

(x₀+y₀-2)²
2

+

(2x₀+y₀-3)²
5

+

(-4x₀+y₀+6)²
17

You are using the 2nd approach I mentioned which involves only two variables. OK, you have a function of two variables that you want to minimize. Using an analogy of a single variable function, what do you know about the derivative at the minimum? Same concept applies to multi-variable problems only you use partial derivatives (thus two equations in the case of two variables). Result should be two equations in x₀ and y₀ that can be solved by substitution. Pure algebraic solution. You are almost there.

actually.. what is on the other side of the = sign, lol?

Other side of the equal sign is the symbol representing the function to be minimized. Use whatever you want, doesn't matter.

 

[takbq2]

I got (1.04,2.55). I'm going to try to check it.

 

[takbq2]

uh.. hmm. how can I check it? I tried against plots of the lines using an array of arbitrary x's. It doesn't seem right.

 

[takbq2]

i did something wrong. chain rule still applies to partial derivatives right?

 

[hotvette]

i did something wrong. chain rule still applies to partial derivatives right?

You have a function with two variables (x₀ and y₀). I don't see how the chain rule is needed.

uh.. hmm. how can I check it? I tried against plots of the lines using an array of arbitrary x's. It doesn't seem right.

There are a couple of practical ways to check. One is to verify that the expressions for the partial derivatives are indeed zero using the values of x₀ and y₀. The other way is to calculate the sum of distances and see if the sum increases or decreases with small changes in both directions of x₀ and y₀. That's basically a way to numerically determine the partials are zero. Better yet, plot sum of square distances as a function of x₀ and y₀ keeping each one constant while varying the other. You should see a nice parabolic looking plot in each case.

I got (1.04,2.55). I'm going to try to check it.

I got a different answer.

 

[takbq2]

when I am taking the partial derivative of, say, x and the function is, say, (4x-2y)²

is the partial derivative not 2(4x-2y)*4

 

[takbq2]

Sweet, I found a mistake in my calculation. I have something to go of of.

 

[takbq2]

This time I got (1.517,0.317). It is still wrong, though, graphically the y-coordinate looks correct. I am stuck :S

 

[hotvette]

when I am taking the partial derivative of, say, x and the function is, say, (4x-2y)² is the partial derivative not 2(4x-2y)*4

Yeah, you're right. I do it so automatically anymore I don't even realize I'm using the chain rule. My goof.

This time I got (1.517,0.317). It is still wrong, though, graphically the y-coordinate looks correct. I am stuck :S

That's within 1% of the answers I got. I got 0.042 for sum-of-square-distances. If you plot sum-of-square-distances separately against x₀ and y₀ you should get a plot like this:

 

[takbq2]

too bad, that means I did it right, but my minimization function that I told you/have been using must be wrong. Oh well.

 

[takbq2]

thank you so much for all your time and help, it helped a ton.

 

[takbq2]

wait, so its correct? why is it not correct to take say, a bunch of random x's and plot the lines with those x's then look for where the obvious closest spot then plot the point and see if it looks right?

It must be correct. I understand your checking and plot and it says that the answer is correct. now I just don't understand why my method of checking was erroneous.