#### Doreen Thomas

For over 20 years, Hyam Rubinstein has made a major contribution to the area of network
optimisation, starting with important contributions to the classical Euclidean Steiner tree
problem. This problem is to find the shortest network (tree) __\( T \)__ connecting a given set __\( X \)__ of __\( n \)__
points in the plane. Additional points, called Steiner points, can be added to find the
solution.
The figure below
shows the Steiner tree on three points, __\( A \)__, __\( B \)__ and __\( C \)__ with an
additional Steiner point __\( S \)__.

Applications of this problem have been the layout of telephone networks, pipelines and
roadway networks, and the rectilinear version has been applied to the design of electronic
circuits on VLSI (very large scale integrated) chips. Although there is a finite algorithm
(Melzak’s Algorithm) to find __\( T \)__, the problem has been shown to be NP-complete. On the
other hand, the minimal spanning tree on __\( X \)__, where no additional points are added, can be
found in polynomial time. In the 1980s, mathematicians
E. N. Gilbert
and
H. O. Pollak
from Bell Laboratories, conjectured that the ratio of the Steiner tree to the minimum spanning
tree is at least __\( \sqrt 3/2 \)__, that is the Steiner tree’s length is at most about 13.4% shorter than the
minimal spanning tree’s length. The ratio of __\( \sqrt 3/2 \)__ occurs in the simple example where there
are three given points forming an equilateral triangle. Eminent mathematicians such as
F. K. Hwang
and
R. L. Graham
who were working at AT&T Bell Labs were interested in this
problem, where the application was to private line tariffs.

In 1990, Hyam Rubinstein reviewed a paper on the ratio conjecture for 5 points and he realised that the variational techniques that he used in his work on minimal surfaces could be applied to the Steiner network problem. Hyam had recently kindly agreed to work with Doreen Thomas, who had been awarded a Re-entry Research Fellowship at The University of Melbourne to encourage women to return to academia. This led to Hyam doing research on optimal networks for the next two decades, and to his body of work, from solutions to long- standing fundamental problems (such as the Steiner ratio conjecture) to successful collaborations with the mining industry internationally, designing underground mine access networks.

The variational technique proved to be a crucial tool for attacking the Steiner ratio conjecture. Two principal reasons were these:

If you have a Steiner tree and move a given vertex along it, the length of the corresponding minimum spanning tree (without Steiner points) changes in a way which is very easily computed. Other motions of a vertex also lead to easy control of the way in which the Steiner ratio changes.

In the process of minimising the ratio, one ends up with a multiplicity of minimum spanning trees with many line segments of equal length. The set of all these edges in these trees is a very nice object to work with.

This technique was used by Hyam and Doreen to prove the Steiner ratio conjecture holds
for configurations of six points, and further to show that if __\( n \)__ given points lie on a circle, then
the Steiner ratio conjecture also holds. In 1991,
D. Z. Du
and
F. K. Hwang
published a solution to the Steiner ratio conjecture using this configuration space approach but with convexity as their main idea. However problems have been found with their proof, and the general
Steiner ratio conjecture remains an open problem.

After a term as Head of the Department of Mathematics at The University of Melbourne,
Hyam took a well-deserved sabbatical at the Institute for Advanced Study, Princeton. Here
he tackled another open problem,
R. L. Graham’s
problem on shortest networks for points on a circle. Suppose a configuration __\( X \)__ consists of __\( n \)__ points lying on a circle of radius __\( r \)__. If at
most one of the edges joining neighbouring points has length strictly greater than __\( r \)__, then
the Steiner tree __\( T \)__ consists of all these edges with a longest edge removed. In order to show that
__\( T \)__ is the minimal spanning tree __\( M \)__, a variational approach was used to show the Steiner ratio
for this configuration is at least one, and equals one if and only if __\( T \)__ and __\( M \)__ coincide. The
variational approach greatly reduced the number of possible Steiner trees (different
topologies) that needed to be considered. Together with a student,
Tony Cole,
Hyam went on to generalise this result to convex configurations with radius of maximum curvature __\( r \)__.

By 1996, Nick Wormald had joined the network-optimisation team. In a paper which provides insight into a boundary between an NP-hard Steiner problem and one that is polynomially solvable, Hyam and his colleagues gave a polynomial-time algorithm for solving the Euclidean Steiner tree problem when the terminals are constrained to lie on a fixed set of disjoint finite-length compact simple smooth curves. It was also shown that the problem is NP-hard if the terminals lie on two parallel infinite lines, or on a bent line segment, provided the bend has an angle of less than 120 degrees. In a related paper, it was shown that there is a polynomial algorithm for the traveling salesman when the towns to be visited are constrained to lie on “smooth” roads.

In 1986,
Martin Gardner
wrote an article in Scientific American where he conjectured that
the minimal Steiner tree joining the 81 points at the corners of a checkerboard could be
constructed by joining many replicas of the Steiner tree on the 4 points at the corners of a
square. This Steiner tree has two Steiner points, and we will call it an “__\( X \)__” for reasons which
are obvious from
the figure below
that shows a Steiner tree on four points, __\( A \)__, __\( B \)__, __\( C \)__ and __\( D \)__ with 2
Steiner points __\( S1 \)__ and __\( S2 \)__.

F. Chung
and
R. Graham
had results on Steiner trees for __\( 2{\times}n \)__ rectangular arrays (ladders),
but were unable to solve the general problem, though they gave some conjectured
solutions to the __\( n{\times}n \)__ problem. Together with Nick, Doreen and two new members of the
network-optimisation team,
Jia Weng
and
Marcus Brazil,
Hyam published three seminal papers on __\( m{\times}n \)__ arrays and more general lattice sets.
The first paper answered the
conjecture, showing that each full component (where each vertex is of degree one; the
smallest irreducible blocks from which the Steiner tree is composed) is indeed the minimal
Steiner tree for the vertices of a square if and only if __\( m=n= 2k \)__. This was generalised to
square or rectangular arrays of integer lattice points where small components other than __\( X \)__s
were needed. In some sense an __\( X \)__ is the most efficient component but, when __\( n \)__ is other than
__\( 2k \)__, other components with “excess” length are needed.
Martin Gardner,
in the book “The Last Recreations: Hydras, Eggs and Other Mystifications”,
described the solution to the
Steiner ratio conjecture as well as the solution to the checkerboard problem as “the two
most important contributions to the Steiner problem in the decade”.

In 2000, David Lee, from the University of South Australia, suggested to the network-optimisation team that they should apply their research to the design of the access network in underground mines. The access network in an underground mine, such as a gold or copper mine, is made up of a network of tunnels and shafts used to access the ore as well as to haul the ore back to the surface. The network of tunnels links fixed access points which are given by the mining engineers with a surface portal. The tunnels are gradient- and curvature-constrained due to the large haulage vehicles. Typically the gradient is 1:7 and the radius of curvature is around 25 meters. Hyam, together with his colleagues developed the fundamental theory of 3-dimensional gradient-constrained networks which are used to model underground mines at a strategic level. In addition, the theory developed by Lester Dubins (so-called Dubins paths, which gives the shortest curvature-constrained path in the plane joining two directed points) was extended to gradient-constrained paths in 3-dimensional space. The theory underlies algorithms developed to determine minimum-cost curvature and gradient-constrained networks in 3 dimensions, where the minimum cost includes both the development costs and the haulage costs over the life of the mine.

Peter Grossman was appointed to work with the team on the mining problem, and write the code to implement the algorithms that design the mining networks. Hyam and his colleagues developed three software tools: UNO (Underground Network Optimiser), which gives the best topology linking points in three-dimensional space with a gradient-constrained network; DOT (Decline Optimisation Tool), which gives a gradient- and curvature-constrained path linking access points on various equally spaced levels underground; and PUNO (Planar Underground Network Optimiser) which gives networks, Steiner trees, and linking points on a mining level. For three years from 2008, Hyam led a large industry project through AMIRA (an association of mining companies that sponsors research projects) to develop the software to a commercial level. The following companies have sponsored the software development and research on this problem: Newmont Australia Limited, Rio Tinto, Oz Minerals, BHP Billiton, Barrick Gold, Vale Inco, Xstrata, Rand and Tribune.

Hyam’s contribution to fundamental research on Steiner tree problems and more general network optimisation problems, as well as the mining application, has been profound. His leadership and dedication to this work and his ability to continually find funding for the project over more than twenty years has been remarkable. The network-optimisation team is so fortunate to be able to work with Hyam and we look forward to the next twenty years.