95-43 Steiner Minimal Trees in Simple Polygons

DIMACS TR: 95-43

Steiner Minimal Trees in Simple Polygons

Author: Pawel Winter

ABSTRACT
An O(n log n) time and O(n) space algorithm for the Euclidean Steiner tree problem with four terminals in a simple polygon with n vertices is given. Its applicability to the problem of determining good quality solutions for any number of terminals is discussed.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-43.ps.gz

DIMACS Home Page