Steiner Trees

Oil Rig

Imagine an oil company building 14 oil rigs, all at once, in the Atlantic Ocean. In the process of building these rigs, the company needs a way to bring the oil on land. They decide to use pipes on the ocean floor. These pipes are so good that they will never fail, never clog up or erode, so there's no need to build a secondary pipe net. Because these never failing pipes are so expensive, the company want a connection with the rigs, that uses the shortest length of pipes. A pipe may split up and unify, i.e. capacity is of no issue. How does the company decide the shortest path from all 14 oil rigs to land?

Even though the above example is the Euclidian problem, we will concentrate on the Rectilinear Steiner Tree (RSMT) problem, which says, to supplement the example, that the pipes only point north, south, east and west. The site is meant as an introduction to the subject using applets, so for details about methods and algorithms see the links page. We have created a notation, the reader should be familiar with before viewing any applets.

It would help the reader to know and understand Minimum spanning trees (MST).