Re: [Algorithms] A computational geometry problem

[Danny K. <dr...@we...>]

>> Problem: Given n lines, determine a point minimizing the summation of the
>> distances from the point to the n lines.
>>
>
> This is a Least Absolute Deviations problem, which are normally solved by
> simplex methods; see the Wikipedia page for more details. If an O(n^3)
> running time is acceptable to you, however, a minimal solution will always
> be found at the intersection of two of the lines, so you can just check 
> all
> the intersection points if you like.

What if the lines are parallel? For two parallel lines, any point between or 
on the lines will solve it, for three it'll be a point on the middle line, 
etc.

Sounds like an odd thing to want, really - there's presumably often lots of 
these points. Under what circumstances might one look for this rather than, 
say, a least squared distance?

<relurk>
Danny