Ein anderes klassisches Optimierungsproblem für eine Menge von Punkten
ist das sogenannte Matching. Hierbei bildet man eine Menge von disjunkten
Paaren und addiert die Distanzen der Punkte aller Paare. Es ist nun eine
einfache Folge der Dreiecksungleichung, daß die Länge
eines
minimalen Steinersternes nicht kürzer sein kann als die Länge
eines maximalen Matchings. Für den Fall von Manhattan-Distanzen
in der Ebene gilt sogar Gleichheit, für den Fall von euklidischen Distanzen
sieht man leicht, daß es Beispiele gibt, für die
gilt.
Motiviert durch Probleme aus dem Kontext optimaler Kommunikationsnetzwerke hatte Suri bereits 1995 nach dem größtmöglichen Wert dieses Verhältnisses gefragt und wiederholte diese Frage im Juni 1998 als besondere Herausforderung auf der Jahrestagung für algorithmische Geometrie. In Zusammenarbeit mit Prof. Henk Meijer (Queen's University, Kanada) gelang es uns zu beweisen, daß das genannte Verhältnis den Wert nicht überschreiten kann, was die bestmögliche Abschätzung ist.
Darüber hinaus fanden wir eine ganze Reihe von weiteren (zum Teil scharfen) Abschätzungen für die Verhältnisse zwischen minimalen Sternen, minimalen Steinersternen und maximalen Matchings; je nach Metrik und Dimension des Raumes ergeben sich dabei sehr unterschiedliche Werte.