Current pedestrian navigation systems assist single users only, despite the fact that people often go out together. For establishing navigational assistance for people who meet, a formalisation of the spatial aspects of meetings is conducted. This formalisation, the meeting tree problem, can be reduced to the minimum Steiner tree problem in euclidean networks. Exact algorithms for the solution of this NP-complete problem exhibit a runtime which is too high for practical problem instances. Thus, faster approximation algorithms are developed in this thesis and evaluated with respect to runtime and approximation ratio. Amongst others, the following algorithms are compared to each other: an approximation in the euclidean plane, methods of stochastic local search (including stochastic hillclimbing and iterated local search) for optimizing e.g. approximations based on minimum spanning trees, a version of the Loss Contracting Algorithm, which has been extended by problem specific heuristics. Results show that approximation ratios which deviate by less than one percent from the optimal solution can be reached.

Aktuelle Fußgängernavigationssysteme unterstützen nur einzelne Benutzer, obwohl Menschen oft in Gruppen unterwegs sind. Um Navigationsassistenz auch für Menschen, die sich tre↵en, anzubieten, entwirft diese Arbeit eine Formalisierung des räumlichen Treffvorgangs und führt diese auf das Steinerbaumproblem in euklidischen Netzwerken zurück. Bekannte exakte Lösungsverfahren für dieses NP-vollständige Problem weisen für den praktischen Einsatz zu hohe Laufzeiten auf. Deshalb werden in der vorliegenden Arbeit schnellere approximative Algorithmen entwickelt und hinsichtlich Laufzeit und Approximationsfaktor evaluiert. Es werden unter anderem eine Approximation in der euklidischen Ebene, Verfahren der Lokalen Suche wie Stochastisches Bergsteigen und Iterative Lokale Suche zur Verbesserung von Approximationen wie beispielsweise Minimalen Spannbäumen, und eine um Heuristiken erweiterte Version des Loss Contracting Algorithmus miteinander verglichen. Dabei werden Approximationsfaktoren erreicht, die je nach Algorithmus und Netzwerk weniger als ein Prozent von der Optimallösung abweichen.