## Re: [Algorithms] A computational geometry problem

 Re: [Algorithms] A computational geometry problem From: Danny Kodicek - 2009-08-25 22:33:21 ```>> 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? Danny ```

 [Algorithms] A computational geometry problem From: J.-R. Jiang - 2009-08-22 12:36:48 ```Dear Colleagues, I am solving the following problem by a computer program. Has anybody known of any algorithm that can solve the problem? Problem: Given n lines, determine a point minimizing the summation of the distances from the point to the n lines. Regards, Jehn-Ruey Jiang Department of Computer Science and Information Engineering National Central University Jhongli City, Taoyuan, 320, Taiwan ```
 Re: [Algorithms] A computational geometry problem From: Ben Sunshine-Hill - 2009-08-22 15:38:21 Attachments: Message as HTML ```On Sat, Aug 22, 2009 at 8:17 AM, J.-R. Jiang wrote: > 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. Ben ```
 Re: [Algorithms] A computational geometry problem From: Danny Kodicek - 2009-08-25 22:33:21 ```>> 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? Danny ```