Finden eines optimalen Standorts

Folgende Aufgabe besteht:

Ziel ist es nun, den optimalen Standort bzw. die optimalen Standorte für einen neuen Punkt Pneu zu finden, der im Vergleich zu den anderen Punkten P den kleinsten Abstand zu maximal vielen Punkten K hat.

Hierzu werden zunächst die Bisektoren zwischen den Punkten P bestimmt. Anhand dieser wird für jeden Punkt Ki (0 ≤ im) der am nächsten gelegene Punkt PKi ermittelt.

Nun bilden wir für jeden Punkt Ki ein Intervall IKi, welches vom Punkt Ki bis zum nächstgelegenen Punkt PKi und genauso weit in die andere Richtung reicht (bsp: [PKi, Ki, PKi+Ki]). Wenn man den neuen Punkt Pneu nun in ein Intervall IKi setzt, liegt Pneu näher an Ki als der bisherige Punkt PKi.

Somit können wir maximal viele Punkte aus K für uns beanspruchen, wenn wir den Punkt Pneu in maximal viele Intervalle gleichzeitig positionieren. Durch einen Sweep, der als Ereignisse Anfang und Ende jedes Intervalls verwendet, lässt sich eine oder ggf. mehrere Stellen (bzw. Intervalle) finden, an denen sich maximal viele Intervalle IKi überlappen. In eine dieser Stellen wird Pneu positioniert.

Im Applet sind die Punkte P als große schwarze Punkte dargestellt, die Punkte K sind als rote Striche dargestellt und die Intervalle, die für den neuen Punkt Pneu optimalen Position, an denen sich die meisten Intervalle überlappen, werden blau dargestellt. Außerdem wird angezeigt, wie viele Kunden maximal für sich beansprucht werden k&önnen und wieviele optimale Intervalle es gibt.
Die Punkte aus P und K sind nicht vorgegeben sondern werden zum Start des Applets und bei einem Klick auf "New Scene" zufällig generiert.

Autoren: Felix Bachmann, Sebastian Gelf