## Digging the shortest trench to uncover a pipeline

Imagine a straight run of pipeline which is buried underground at a depth of 2 meters. Imagine also, that the pipeline passes somewhere through a circular plot of land but that the exact location of the pipeline is not known. How would one go about finding it? This problem is discussed in detail in article by Ian Stewart on page 206 of the September 1995 issue of Scientific American . One strategy would be to dig a ditch 2 meters deeps around the perimeter of the entire circular plot of land. Since the pipeline is known to pass under this area, the ditch is uncover part it. If the circular plot ofland has a 1 kilometer radius then the proposed ditch will be approximately 6.28 km. long. Is it possible to dig a shorter ditch which is also certain to discover the location of the pipeline?

It may at first seem that the answer is surely negative; in other words, digging a circular ditch around the perimeter is the most efficient means of discovering the location of the pipe line. After all, digging a ditch of smaller radius may fail to detect a ditch which passes through only a small part of the circular area. The same is true for a ditch dug along a diameter. Before looking at a solution, you should take some time to see if you can discover how to dig a shorter ditch which is certain to discover any straight pipeline passing through the circular area. (Hint: The length of this ditch is approximately 5.14 km.)

However, there may be even shorter solutions. One possible approach to finding an even shorter solution is to consider a trench composed of a circular part and three straight segments . First, convince yorself that any such trench will actually detect all straight pipelines. Then, find a particular configuration whose total length is less than 5.14 km. Is this the best possible? See Scientific American February 1996 page 125 for a strategy for constructing an even shorter trench which uses a circular segment connected to two tangent line segments as well as two disjoint line segments. Even this is not known to provide a minimal solution.

Before looking at the solution, take some time to think how you would go about solving this problem. This will help you understand the final offered solution. You may even come up with a better solution.

Juris Steprans