Finding a minimal tree in a polygon with its medial axis.
Herman J. Haverkort, Hans L. Bodlaender · 1999
In order to solve a problem arising when generalizing to-pographical maps, we consider the following problem for simple polygons, i.e., coherent polygons without holes. Some edges of the polygon may be marked as hard, and at least two vertices of the polygon are marked as ter-minals. We show that the problem to nd a tree of minimum total length, spanning the hard edges and ter-minals, using only edges of the polygon and its medial axis, can be stated as the problem to nd a minimum Steiner tree in a Halin graph, and can be eÆciently solved in linear time. Keywords map generalisation, minimum network Steiner tree,