Abstract: Wir untersuchen das Problem, Mobilfunkantennen auf einem gegebenen Gelände zu plazieren. Das Ziel dabei ist die Minimierung der Anzahl der zur vollständigen Überdeckung des Geländes benötigten Antennen. Wir zeigen, dass schon für einfache Wellenausbreitungsmodelle dieses Problem NP-hart ist. Mehr noch: Keine akzeptable Approximation kann in Polynomzeit berechnet werden, asymptotisch im schlimmsten Fall. Der Not gehorchend schlagen wir daher Heuristiken vor, und wir zeigen, welche Lösungen dies für reale Gelände (wie etwa die Schweiz) und typische Wellenausbreitungsmodelle (wie etwa das Hata-Modell) liefern.
Abstract: Den Nächsten Nachbarn zu einem spezifizierten Punkt q \in Rd in einer gegebenen Menge P \subset Rd von Punkten zu finden, ist ein geometrisches Problem, das in vielen Anwendungen, wie zum Beispiel bei Ähnlichkeitsanfragen in multimedialen Datenbanken, bei der Mustererkennung, beim Data Mining, bei der Video Kompression und beim Information Retrieval auftritt. In den meisten Anwendungen ist die Dimension d des Suchraumes sehr groß. Eine von vielen Algorithmen benötigte in d exponentielle Laufzeit oder Vorverarbeitungszeit oder ein oft benötigter in d exponentieller Speicherbedarf verbieten sich daher. Der Vortrag wird eine Übersicht über die bekannten Algorithmen und Datenstrukturen für das Nächste Nachbar Problem in einem hochdimensionalen Raum geben. Anschließend werden erste eigene Resultate in diesem Zusammenhang präsentiert.