Re: [Algorithms] A computational geometry problem

[Ben Sunshine-H. <sn...@gm...>]

On Sat, Aug 22, 2009 at 8:17 AM, J.-R. Jiang <jr...@cs...>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