Mathe

Hallo zusammen,

ich rätsele z.Z. an einer an sich recht einfach zu formulierenden Aufgabe
herum:

Gegeben sei eine Reihe von Meßstationen an verschiedenen Punkten im R3:
p_1,...,p_N (also jeder Punkt in der Form p=(x,y,z)).
An jedem dieser Meßpunkte wurden verschiedene Meßgrößen s_1,...,s_M (also
ein Vektor <s> ) erfaßt, die alle in derselben Einheit vorliegen, z.B. die
Konzentration eines bestimmten Schadstoffes.

Außerdem wurde an einer unbekannten Stelle q=(x_0,y_0,z_0) im Raum eine
Probe dieser Meßgrößen <t> ermittelt: t=<t_1,...,t_M>

Gesucht ist nun die dem Punkt q am nächstgelegene Meßstation (oder
allgemeiner: Die k nächstgelegenen Meßstationen).

Das Problem "brute force" zu lösen ist einfach: Man ermittelt für *alle*
Punkte p_1,...,p_N jeweils den Abstand ihres zugehörigen Meßwertvektors
<s> zu <t> , sortiert aufsteigend in diesen Abweichungen und die ersten k
Werte sind die gesuchten. Aber da N sehr groß werden kann, verbietet sich
eine solche ineffiziente Suche, d.h.: clevere Lösungen sind gesucht.

Zusatzfrage für die Oberknobler: Die einzelnen Schadstoffe s_1,...,s_M
werden an M bekannten fixen Punkten im Raum emittiert. Unter idealen
Umgebungbedingungen würde ihre Konzentration abhängig von der Entfernung
zur Austrittsstelle nach einer bestimmten nichtlinearen Funktion abfallen,
z.B. proportional zu 1/R^3. Ist das oben beschriebene "simple" euklidsche
Abstandmaß (also: d(p,q)=sqrt( (x1-x2)² + (y1-y2)² + (z1-z2)² ) überhaupt
das beste?

Danke für Eure Ideen,
Kai

jogix

Hi Kai,

ich sehe im Moment wenig Chancen, die nächstgelegene Meßstation anders zu ermitteln, als wie von Dir erwähnt. Außer, die Meßstationen liegen örtlich gesehen auf einer "Kurve" oder "Funktion", dann könntest Du daraus ab gewissen Punkten schließen, ob es Sinn macht, die weiteren Meßstationen zu überprüfen oder weiter hinten fortzufahren. Beispiel:
alle Meßstationen liegen auf einer geraden. Du suchst die Meßstationen der Reihe nach ab, bis Du das Maximum erreichst, sobald Du die erste Meßstation mit fallenden Werten erreichst, brichst Du die Suche ab, da die Ergebnisse nicht besser werden.

Die Abstandsermittlung, wie Du sie genannt hast, ist schon richtig so, da die nichtlineare Funktion, mit der die Konzentration nachläßt, nichts mit der Berechnung des Abstandes zu tun hat. schließlich ist das *die* Formel zur Berechnung des Betrages im R3. Du kannst allerdings, bei sinnvoller Verteilung der Meßstationen wie oben genannt, die oben beschriebene optimierung des Algorithmus erreichen, sprich weniger Berechnungen durchführen.

Jester

Nun, da Du die Positionen bereits vorher zu kenn scheinst ist eine Vorbearbeitung möglich. Mit dieser kannst Du den Aufwand sogar auf O(log n) drücken.

Stichwort: Voronoi-Gebiete

Ich skizziere hier einfach mal nen Algorithmus für die Ebene, denke aber, daß dieser sich problemlos auf höhere Dimensionen verallgemeinern läßt.

Wir sortieren zunächst die Punkte nach ihrer x-Koordinate. Dann fügen wir den Median als Knoten in einen Baum ein. Die Menge ist jetzt praktisch in zwei Teiler zerlegt. Diese sortierst Du jetzt jeweils nach der y-Koordinate. Median wird rechts bzw. link unter der Wurzel einsortiert. Die übrigbleibenden Punkte werden wieder nach x sortiert, Mediane einfügen, weitere Teile sortieren...
immer abwechselnd nach x und y. Das gibt dann einen schönen Baum.

Wenn Du jetzt einen Punkt gegeben hast, dann mußt Du im Prinzip nur diesen Baum durchwandern und entscheiden, in welchem Halbraum Du liegst. Allerdings mußt Du etwas vorsichtig sein, weil die Halbräume nicht sofort ausscheiden. Am besten malst Du Dir das ganze mal auf und zeichnest die Trennungen durch waagrechte / senkrechte Striche ein.

Wenn Du jetzt den gefunden Punkt rauslöschst kannst Du mit diesem Algorithmus auch den 2. nächsten Punkte usw. rausfinden, das geht dann in O(k*log n).

Zu der Zusatzfrage: Allgemein ist dieses Abstandsmaß schon sinnvoll, aber je nach Anwendung könnte es vielleicht auch Sinn machen die Schadstoffkonzentration als Abstand aufzufassen. Mußt Du aber vorsichtig sein, daß auch alle wichtigen Eigenschafteb einer Norm erhalten bleiben. Da wär ich glaub ich lieber vorsichtig.

MfG Jester