Steiner reducing sets of minimum weight triangulations: Structure and topology

This paper defines and classifies the topology of the Steiner reducing set corresponding to a finite planar point set and its minimum weight triangulation. A Steiner point P is a Steiner reducing point of a planar point set X   if the weight (sum of edge lengths) of a minimum weight triangulation of X∪{P}X∪{P} is less than that of X. The Steiner reducing set  St(X)St(X) is the collection of all Steiner reducing points of X  . We prove a structure theorem providing alternate geometric conditions for membership in the Steiner reducing set. We prove that St(X)St(X) can be topologically complex, containing multiple connected components or even holes. We construct families of sets X   for which the number of connected components of St(X)St(X) grows linearly in the cardinality of X  . Moreover, we prove that when St(X)St(X) is not simply connected, the rank of H1(St(X))H1(St(X)) (i.e. the number of holes) can also grow linearly in the cardinality of X. Lastly, we give an example illustrating that the geometric conditions do not translate simply into conditions sufficient to completely characterize the Steiner reducing set.