The Water Pipes Problem
We were given the job of figuring out the minimum amount of water
pipe necessary to connect up the houses on a street to a water main. We
had to determine where to dig a straight trench down the street for the
water main pipe. The houses are set back from the street by
varying distances, and ideally each house should be about 5 meters from the
water main. The problem was to find the trench that would result in the
minimum usage of water pipe segments from the main to the houses, and
the total length of the pipe needed.
We have the (x,y) coordinates of the connections to the houses stored
in a file, "HOUSES.DAT". Remember from plane geometry that the distance from
point (x,y) to a straight line with slope A and y-intercept B is given by
D = |A*x+B-y|/sqrt(A^2+1)
to minimize the connecting pipe lengths by varying the free parameters A
and B. The following small script does just that:
LENGTH_GOAL = 5 ! try to achieve this goal
READ\-MESSAGES houses.dat X Y ! read in the house positions
SCALAR\FIT A B ! declare the free parameters
A = 1 ! initialize
B = 1 ! initialize
D[1:LEN(X)] = LENGTH_GOAL !
DISTANCE = 'ABS(A*X+B-Y)/SQRT(A*A+1)' !
FIT\-MESSAGES D=SQRT(DISTANCE) ! do the fit
FIT\UPDATE PIECES ! redo using calculated A and B
STATISTICS PIECES PSUM\SUM ! the total length of pipe needed
DISPLAY 'Total length of pipe = '//RCHAR(PSUM,'%4.2f')
Since least squares is used for fitting, we take the square root of the
expression. Note that we have more than one independent variable in the
expression. Extension to multidimensional cases is straightforward.
The problem of fitting to a scattered set of points with a straight line
which is, on the average, a fixed number of units away will, in general,
have two solutions, and which one you get will depend on the starting values
of the free parameters.
Click here to upload the Extrema code that performs
Click here to upload data for house coordinates.