views:

205

answers:

1

Hi, I'm writing a solution for the Usaco problem "Electric Fences". In the problem you have to find the optimal location for a point among a large amount of linesegments, so the sum of point-linesegment distances is smallest possible.

I had an idea, that it might be possible to do a hillclimb, and it worked for all testcases. The given analysis used a similar method, but it did not explain why this would work.

Thus I'm still unable to either prove or disprove the existence of local optimums in the given tasks. I had an idea that it could be done using induction, but I haven't been able to make it work. Can you help me?

Updated definition

Given a set of (x1,y1,x2,y2) linesegments find the (x,y) point P, that minimizes the function:

def Val(x,y):
    d = 0
    for x1,y1,x2,y2 in LineSegments:
        if triangle (x1,y1,x2,y2,x,y) is not obtuse in (x1,y1) or (x2,y2):
            d += DistPointToLine(x,y,x1,y1,x2,y2)
        else:
            d += min(DistPointToPoint(x,y,x1,y1), DistPointToPoint(x,y,x2,y2))
    return d

By some reason the problem contains only one local optima, and thus the following procedure can be used to solve it:

precision = ((-0.1,0), (0.1,0), (0,-0.1), (0,0.1))
def Solve(precision=0.1):
    x = 0; y = 0
    best = Val(x,y)
    while True:
        for dx,dy in precision:
            if Val(x+dx, y+dy) > best:
                x += dx; y += dy
                best = Val(x,y)
                break
        else:
            break
    return (x,y)

The questions is: Why does this not get stuck somewhere on the way to the global optimum? Why is there no local hilltops to bring this naive procedure to its knees?

+4  A: 

It is easy to prove the algorithm's correctness if we notice that the distance function for a single line segment is a convex function. Convex in this case means that if we think of the distance function as a surface z=f(x,y), then if we filled in the volume above the surface, we'd have a convex solid. In the case of the distance from a single line segment, the solid would look like a triangular wedge with conical ends.

Since the sum of convex functions is also convex, then the sum of distances from multiple line segments will also be a convex function. Therefore, any local minimum you find must also be a global minimum by virtue of the function being convex.

Theran
You mean convex in some kind if three dimensional sense?Also, if''(x)=0 (like a triangle), is it not both convex and concave?
Thomas Ahle
Yes, if we look at the function as a 3d surface it carves out a convex volume of space. I'm not sure what the function would look like for a triangle of line segments, but it must also be convex based on the sum property. I've updated my answer to reflect this.
Theran
This looks correct! Convexity is well defined for R^n. Also, I just looked up, for convex functions, a local minimum is also a global minimum. I will delete my answer.
Moron
I see, it is a bit different from what I thought of as 'convex' since it is multi dimensional, not strictly convex and not differentiable, but I believe I can use this new knowledge for a lot of things in the future. Thanks a bunch!
Thomas Ahle