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?