The Water Pipes Problem

The 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.

Solution: 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)

We want 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.