A MODIFIED MELZAK PROCEDURE FOR COMPUTING NODE-WEIGHTED STEINER TREES

Given a set B of points in the Euclidean plane, the standard Steiner P roblem asks for a network of minimum length connecting the points of B . A solution to this problem is called a Steiner Minimal Tree and may be computed exactly, using Melzak's compass-and-straightedge methods. A Steiner Tree often contains additional nodes, called Steiner points, not belonging to B. The node-weighted Steiner problem asks for the ne twork connecting the points of B which minimizes the energy E = length + alpha(number of Steiner points), where a is a fixed nonnegative wei ght. Solutions to this problem, here called node-weighted Steiner tree s, can have different geometries than those available to standard Stei ner trees. This paper presents a modified Melzak procedure which compu tes the node-weighted Steiner tree for a given set B. (C) 1996 John Wi ley & Sons, Inc.