Re: A computational geometry problem

>> 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 


------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
trial. Simplify your report design, integration and deployment - and focus on 
what you do best, core application coding. Discover what's new with 
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list