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.