Journal:Informatica
Volume 11, Issue 4 (2000), pp. 469–478
Abstract
The result of simulation of an idealized thin wet film connecting fixed points in the Euclidean plane is a length-minimizing curve. Gradually increasing the exterior pressure we are able to achieve the film configuration near to the Steiner minimal tree. This film evolution may be an interesting tool for solving the Euclidean Steiner problem, but several dead-point situations may occur for a certain location of fixed points. A continuous evolution of the film is impossible by increasing the pressure in these situations. The investigation of dead-point situations gives the ways of overcoming the difficulties of dead-point situations and continuing the film evolution by temporarily decreasing pressure.
Journal:Informatica
Volume 10, Issue 4 (1999), pp. 457–466
Abstract
The Steiner problem asks for the shortest network that spans a given set of fixed points in the Euclidean plane. The problem is NP hard.
The result of simulation of an idealized “wet” film connecting fixed points is a length-minimizing curve. Increasing the exterior pressure step by step we are able to achieve the film configuration near to the Steiner minimal tree. “Dead-point” situations may occur for some symmetric allocation of fixed points.
The limited simulation experiments show that the average computation time depends almost linearly on the number of fixed points for the situations without “dead-points”.