Durchschnittlicher Abstand zum nächstgelegenen Punkt

Neue Frage »

well Auf diesen Beitrag antworten »
Durchschnittlicher Abstand zum nächstgelegenen Punkt
Hallo,

ich habe einen Kreis mit n Punkten, die im Kreis gleichverteilt sind. Nennen wir die Punkte Adressen.

Die mittlere Entfernung zwischen zwei Adressen ist:



r ist der Kreisradius. Ausgerechnet wurde dies von Arthur Dent in diesem thread.

Frage: Wenn nach dem Zufallsprinzip drei Adressen gezogen werden, wie ist mittlere Entfernung der erstgezogenen Adresse zu der jeweils nächstgelegenen Adresse aus zweit- und drittgezogener Adresse.

Klingt sehr theoretisch; ich mache mal einen praktischen Anwendungsfall daraus (mit starren idealisierten Rahmenbedingungen).

Es gibt eine Stadt, deren Fläche ein Kreis mit dem Radius r ist und gleichverteilt über den Kreis gibt es Adressen. In der Stadt gibt es einen Taxifahrer, der sobald er einen Auftrag ausgeführt hat zwischen zwei zwischenzeitlich eingegangenen neuen Aufträgen wählen kann. Er nimmt immer den Auftrag mit der nächstgelegenen Adresse. Wie weit ist durchschnittlich die Anfahrtstrecke zu dieser nächstgelegenen Adresse (als Luftlinie, geometrisch gesprochen als Gerade).

Zur Verdeutlichung: Gäbe es für den Taxifahrer keine Auswahl zwischen zwei Adresse, sondern nur eine Adresse, die er anfahren muss, so wäre die Anfahrtstrecke für ihn (siehe Formel und Link oben):

Ich habe schon -vergebens - verschiedene Ansätze probiert, will diese hier zu Beginn des Threads nicht sofort darstellen, weil das verwirren könnte.

Ich erwarte auch nicht unbedingt den großen Lösungswurf, sondern bin auch für jede Lösungsfährte und jeden Ansatz dankbar. :-)
AD Auf diesen Beitrag antworten »

Ehrlich, das wird in exakter Rechnung der reinste Horror. Da kommen zu dem oben noch zwei Integrale in der Schachtelung hinzu, also ein Fünffachintegral (!).

Hier ist wohl der Zeitpunkt gekommen, das eher über Monte-Carlo-Simulation auszurechnen, das spart Zeit und Nerven. Und ist überdies exakter als (wie gesehen) unzulässige Annahmen wie "Adressen auf Kreislinie mit mittleren Mittelpunktabstand". Augenzwinkern
well Auf diesen Beitrag antworten »

Vielen Dank Arthur!!! Prost

"Monte-Carlo-Simulation". Nie gehört ... Der Begriff gefällt mir. :-)

O.K., meine Monte-Carlo-Simulation sieht so aus:

Excel genutzt.

Spalten angelegt:
- Startpunkt
- Zielpunkt 1
- Zielpunkt 2

Zufallszahlen zwischen 0 und 100 für jeden der drei Punkte.

Spalten, die berechnen:
- Differenz zw. Start- und Zielpunkt 1
- Differenz zw. Start- und Zielpunkt 2

Spalte mit:
- Minimum aus "Differenz zw. Start- und Zielpunkt 1" und "Differenz zw. Start- und Zielpunkt 1"

10.000 mal diese Konstellation gerechnet (natürlich mit wechselnden Zufallszahlen).

Mittelwerte berechnet für:
- Differenzen zw. Start- und Zielpunkt 1
- die Minimums (aus "Differenz zw. Start- und Zielpunkt 1" und "Differenz zw. Start- und Zielpunkt 1")

Ergebnis:
Mittelwert für Differenz zw. Start- und Zielpunkt 1 beträgt 33,7
Mittelwert der Minimums ist 21,2

Das Verhältnis von 21,2 zu 33,7 beträgt 63%. Das bedeutet, dass die Strecke zum nächstgelegenen Zielpunkt bei zwei Zielpunkten nur 63% der Länge hat, wie der Abstand, wenn nur ein Zielpunkt vorgegeben ist.

Ich habe bei der Gelegenheit gleich simuliert, wieviel Strecke man sich einspart bei 3, 4, ... bis 10 Zielpunkten. Bezogen auf 100 % Strecke bei einem Zielpunkt sehen die Ergebnisse für die Strecke zum nächstgelegenen Zielpunkt so aus:
- 2 Zielpunkte: 63 %
- 3 Zielpunkte: 45 %
- 4 Zielpunkte: 35 %
- 5 Zielpunkte: 29 %
- 6 Zielpunkte: 24 %
- 7 Zielpunkte: 21 %
- 8 Zielpunkte: 18 %
- 9 Zielpunkte: 16 %
- 10 Zielpunkte: 15 %

Ich kann gerne erklären, warum ich so vorgegangen bin. Will es nicht gleich hier darlegen, um den Beitrag nicht weiter zu sprengen. Ich erhoffe mir aber kritische Frage, die mich dazu zwingen. Forum Kloppe ;-)

Eins fällt glaube ich gleich ins Auge. Ich bin nämlich der Ansicht, dass es für die Ermittlung der relativen Streckenabweichungen keine Rolle spielt, ob die Fläche ein Kreis, ein Rechteck, ein Dreieck oder sonst was ist. Ich hoffe ich liege damit nicht daneben. verwirrt
AD Auf diesen Beitrag antworten »

Mit modernen Rechnern nimmt man aber ein paar mehr als nur 10000 Simulationen.

Hier mal mein schnell programmiertes Ergebnis deines Problems:

Jeweils drei gleichverteilte Punkte im Einheitskreis, und dann Minimum von 1-2, 1-3 erfasst

Insgesamt habe ich das 1000 x 1000000 = 1 Milliarde mal wiederholt, dabei aus jeweils 1 Million Werte einen Mittelwert gebildet und diese 1000 Mittelwerte statistisch analysiert, um den Simulationsfehler abschätzen zu können. Hier die Resultate:

code:
1:
2:
3:
4:
5:
                      Abstand     2-Minimum    2-Maximum
Mittelwert         :  0.90540      0.67667      1.13412
Standardabweichung :  0.00043      0.00035      0.00038
  5%-Quantil       :  0.90469      0.67608      1.13349
 95%-Quantil       :  0.90609      0.67723      1.13473

Ach ja: Ich komme somit auf . Das weicht beträchtlich von deinen 63% ab - hast du wirklich gleichverteilte Punkte im Kreis simuliert?
well Auf diesen Beitrag antworten »

Sind die 0,90543 die durchschnittliche Strecke bei einem Radius r=1? Also das amtliche Endergebnis für das, was bisher in der Formel gekleidet war?

Und 0,67670 ist die Strecke, wenn von zwei Zielpunkten der nächstgelegene genommen wird?
Das wären 74,7 % der Strecke im Vergleich zur Strecke bei einem Zielpunkt. geschockt Und ich habe 63 % rausgekriegt. Wo liegt der Denkfehler bei meinem Lösungsweg?
AD Auf diesen Beitrag antworten »

Verschoben

Angefangen hat's mit Geometrie, aber jetzt ist es doch eher Stochastik.
 
 
well Auf diesen Beitrag antworten »

Zitat:
Original von well
Sind die 0,90543 die durchschnittliche Strecke bei einem Radius r=1? Also das amtliche Endergebnis für das, was bisher in der Formel gekleidet war?

Und 0,67670 ist die Strecke, wenn von zwei Zielpunkten der nächstgelegene genommen wird?
Das wären 74,7 % der Strecke im Vergleich zur Strecke bei einem Zielpunkt. geschockt Und ich habe 63 % rausgekriegt. Wo liegt der Denkfehler bei meinem Lösungsweg?
AD Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Ach ja: Ich komme somit auf . Das weicht beträchtlich von deinen 63% ab - hast du wirklich gleichverteilte Punkte im Kreis simuliert?
well Auf diesen Beitrag antworten »

Ich habe gleichverteilte Abstände simuliert.

Wie hast Du operiert?
AD Auf diesen Beitrag antworten »

Zitat:
Original von well
Ich habe gleichverteilte Abstände simuliert.

Wo? Auf der Strecke, im Quadrat, im Kreis...

Zitat:
Original von well
Wie hast Du operiert?

Na wie ich hier erläutert habe:

Zitat:
Original von Arthur Dent
für

Simuliert wird also der zufällige Abstand vom Mittelpunkt gemäß dieser Verteilungsfunktion mit Inversionsmethode. Dazu noch ein im Vollkreis gleichverteilter Winkel.

Das jeweils für jeden Punkt (also bis zu 11 Punkte pro Einzelsimulation, wenn man das Minimum von bis zu 10 Abständen ermitteln will).
well Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Zitat:
Original von well
Ich habe gleichverteilte Abstände simuliert.

Wo? Auf der Strecke, im Quadrat, im Kreis...


Na ja, wie ich schon sagte:

Zitat:
Original von well
Eins fällt glaube ich gleich ins Auge. Ich bin nämlich der Ansicht, dass es für die Ermittlung der relativen Streckenabweichungen keine Rolle spielt, ob die Fläche ein Kreis, ein Rechteck, ein Dreieck oder sonst was ist. Ich hoffe ich liege damit nicht daneben. verwirrt
AD Auf diesen Beitrag antworten »

Doch, damit liegst du daneben. Quantitativ kann ich das aber nicht beurteilen, müsste man durch entsprechende Simulationen mal vergleichen.

Jetzt erstmal die Ergebnisse für bis zu 10 Adressen gleichverteilt im Kreis (diesmal nur 100 Millionen Durchläufe):

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
 k  Mittelwert  Std.abw.  5%-Quantil   95%-Quantil
 1  0.90542     0.00042   0.90472      0.90612
 2  0.67670     0.00035   0.67612      0.67726
 3  0.55911     0.00030   0.55860      0.55961
 4  0.48528     0.00027   0.48485      0.48573
 5  0.43371     0.00024   0.43333      0.43411
 6  0.39520     0.00022   0.39483      0.39555
 7  0.36508     0.00020   0.36475      0.36540
 8  0.34072     0.00019   0.34041      0.34102
 9  0.32053     0.00018   0.32021      0.32081
10  0.30343     0.00017   0.30315      0.30372

 k  relativ zum mittleren Abstand nur einer Adresse
 1  1.0000
 2  0.7474
 3  0.6175
 4  0.5360
 5  0.4790
 6  0.4365
 7  0.4032
 8  0.3763
 9  0.3540
10  0.3351


EDIT: Und hier mal eine kleine Formabhängigkeitsuntersuchung der relativen Abstände:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
 k  Kreis   Quadrat   Rechteck 1x3   Rechteck 1x10   nur Linie   
 1  1.0000  1.0000    1.0000         1.0000          1.0000
 2  0.7474  0.7464    0.6890         0.6382          0.6250
 3  0.6175  0.6170    0.5444         0.4711          0.4500
 4  0.5360  0.5355    0.4607         0.3767          0.3500
 5  0.4790  0.4784    0.4055         0.3166          0.2857
 6  0.4365  0.4356    0.3659         0.2751          0.2411
 7  0.4032  0.4021    0.3359         0.2449          0.2084
 8  0.3763  0.3751    0.3121         0.2220          0.1834
 9  0.3540  0.3526    0.2926         0.2039          0.1637
10  0.3351  0.3336    0.2763         0.1893          0.1477

Wie ersichtlich, gibt es zwischen Kreis und Quadrat kaum Unterschiede, jedenfalls nicht im Rahmen der Genauigkeit dieser Simulation. Bei nichtquadratischen Rechtecken (hier 1:3 und 1:10) sieht man dann aber schon immer größere Abweichungen.

Und wenn ich mir die letzte Spalte so ansehe, dann weiß ich auch wie du simuliert hast: nur eindimensional

Das kann man nun aber auch wieder theoretisch ausrechnen, mit etwas Mühe.
well Auf diesen Beitrag antworten »

Ups, da habe ich also die Strecken auf der Linie simuliert,... Danke für die Aufklärung und die Simulationen für verschiedene Flächen.

Hm, ...., kann es sein, dass meine Annahme - neben der Linie - auch gelten würde, wenn die Fläche unendlich ist?

In Excel würde ich lange rum machen müssen, um eine kritische Anzahl von Simulationen hinzukriegen. Wenn ich trotzdem mal rum simulieren will, müsste ich dann diese Formel von Dir nehmen

und mir per Zufallsgenerator für und Variable zwischen 0 und 1 und für den cos Werte zwischen 0 und 180 Grad geben lassen?
AD Auf diesen Beitrag antworten »

Zitat:
Original von well
In Excel würde ich lange rum machen müssen, um eine kritische Anzahl von Simulationen hinzukriegen. Wenn ich trotzdem mal rum simulieren will, müsste ich dann diese Formel von Dir nehmen

Richtig.

Zitat:
Original von well
und mir per Zufallsgenerator für und Variable zwischen 0 und 1

So einfach ist es nicht: Ich hatte doch oben schon geschrieben, wie es geht:

Zitat:
Original von Arthur Dent
Zitat:
Original von Arthur Dent
für

Simuliert wird also der zufällige Abstand vom Mittelpunkt gemäß dieser Verteilungsfunktion mit Inversionsmethode.

Im Endeffekt bedeutet das für in Excel für diesen Mittelpunktsabstand: =WURZEL(ZUFALLSZAHL())

Zitat:
Original von well
und für den cos Werte zwischen 0 und 180 Grad geben lassen?

Das ist wieder richtig. Aber Obacht: Exel rechnet bei Winkelfunktionen gewöhnlich im Bogenmaß!
well Auf diesen Beitrag antworten »

Herzlichen Dank Arthur,

wenn es solche Menschen wie Dich nicht gäbe, wäre ich ein wenig dümmer geblieben und hätte einen haufen Zeit verloren.

Morgen werde ich gemäß Deinen Vorgaben in Excel rumsimulieren. Jetzt gehe ich Schläfer

Ähm, nur interessehalber: Kann es Deiner Ansicht nach stimmen, dass mein Vorgehen für die relativen Streckenabweichungen nicht nur für die Linie, sondern auch für eine unendliche Fläche Geltung hat?
AD Auf diesen Beitrag antworten »

Ich muss meine vorschnell geäußerte Meinung revidieren:
Im unendlichen könntest du tatsächlich recht haben mit den Werten von der Linie. Allerdings muss da erstmal das Problem genau definiert werden, denn eine Gleichverteilung in der unendlichen Ebene gibt es nicht. Für die dich interessierenden Abstandsverhältnisse gibt es da aber ein Ersatzmodell, was dem von dir gewünschten Sachverhalt entspricht. Aber das dann erst morgen...
AD Auf diesen Beitrag antworten »

Ok, zum Problem der "Gleichverteilung" in der unendlichen Ebene. Wie oben erwähnt, gibt es die eigentlich nicht.

Was du machen kannst, ist die Betrachtung eines Poisson-Punktprozesses in der Ebene. Viel bekannter ist der eindimensionale Poissonprozess , wo der Parameter in der Regel die eindimensionale Zeit darstellt (siehe z.B. Wikipedia-Beitrag). Hier meine ich aber wie gesagt den in der Ebene, oder allgemeiner im (Suchbegriff "spatial poisson process"). Der ist charakterisiert durch folgende Eigenschaften
  • Die Anzahl der Punkte innerhalb einer messbare Teilmenge des ist poissonverteilt mit Parameter ; dabei ist das Lebesgue-Maß (also das n-dimensionale Volumen) und die Intensität des Poissonprozesses, das entspricht der mittleren Punktanzahl pro Volumeneinheit.
  • Sind die -Teilmengen disjunkt, dann sind die Anzahlen unabhängig.

Dieses Modell hier für die Ebene (also n=2) angesetzt, lässt sich die Verteilungsfunktion des Abstand eines Punktes zum nächsten Nachbarn einfach berechnen:



Dabei ist die n-dimensionale Kugel um den Ursprung mit Radius , im zweidimensionalen einfach ein Kreis mit Flächeninhalt . Dann lässt sich auch der mittlere Abstand bestimmen:



Das Minimum von Abständen entspricht dann der -fachen Intensität des Poisson-Prozesses, d.h., . Hier ergibt sich für das Verhältnis der mittleren Abstände dann ganz einfach

, also hinsichtlich der obigen Listen dann

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
 k  relativ zum mittleren Abstand nur einer Adresse
 1  1.0000
 2  0.7071
 3  0.5774
 4  0.5000
 5  0.4472
 6  0.4082
 7  0.3780
 8  0.3536
 9  0.3333
10  0.3162
well Auf diesen Beitrag antworten »

Guten Morgen Arthur,

das mit dem Abstand in der unendlichen Ebene ist interessant. Intiutiv und unmathematisch ausgedrückt würde ich sagen, dass es gerechnet wird ein "Kreis ohne äußeren Rand" (bzw. "unendlicher Kreis"). Die mittlere Entfernung beim "unendlichen Kreis" ist deshalb kleiner als beim Kreis, weil beim Kreis für Startpunkte, die im Randgebiet liegen, Zielpunkte ausserhalb dem Randgebiet nicht da sind, mit der Konsequenz, dass weitentfernte Zielpunkte weniger häufig vorkommen als bei dem "unendlichen Kreis".
Klingt möglicherweise seltsam, aber ich kann mich nicht gut mathematisch klar ausdrücken. :-/

Ich habe heute morgen in Excel mit Hilfe Deiner Vorgaben simuliert. Bei einem Ziel stimmt meine mittlere Strecke mit Deinem Simulationsergebnis überein, bei 2 und mehr Zielen jedoch leider nicht. Irgendwo muss ich bei meinem Vorgehen einen Denkfehler drinhaben. Ich erklär meine Schritte mal anhand einer einzelnen Simulation bei 3 Zielpunkten (x2, x3 und x4 sind die Zielpunkte; der Startpunkt heißt x1):

Folgende Zahlen simulierte ich mit dem Zufallsgenerator:
- =157,9
- r für x1 = 0,61
- r für x2 = 0,15
- r für x3 = 0,07
- r für x4 = 0,44

Die Wurzel daraus ist jeweils:
- x1 = 0,78
- x2 = 0,38
- x3 = 0,27
- x4 = 0,66

Mit der Formel

kriege ich den Abstand zwischen x1 und x2. Die Formel nutze ich genauso für die Abstandsermittlung zwischen x1 und x3 sowie zwischen x1 und x4.
Ich erhalte
- Strecke x1 nach x2: 1,15
- Strecke x1 nach x3: 1,04
- Strecke x1 nach x4: 1,42
Ergebnis: Die minimale Enfernung besteht zwischen x1 und x3, nämlich 1,04*r.

1000 mal habe ich so simuliert und den Mittelwert gebildet: Er beträgt 0,76*r (für den nächstgelegenen Zielpunkt bei 3 Zielpunkten).

Bei einem Zielpunkt komme ich auf 0,8955, also sehr nahe an Deinem Simulationsergebnis.
Bei den anderen Simulationsergebnisse liege ich jedoch weit daneben:
- 2 Zielpunkte: 0,80
- 3 Zielpunkte: 0,76
- 4 Zielpunkte: 0,73
- 5 Zielpunkte: 0,71
- 6 Zielpunkte: 0,69
- 7 Zielpunkte: 0,68

Wo steckt bei mir der Wurm drin? :-(

Dann noch eine Bitte: Kannst Du Deine Höllenmaschine anwerfen, und auch die Ergebnisse für 11 bis 20 Zielpunkte ausspucken lassen?
AD Auf diesen Beitrag antworten »

Wenn du drei Entfernungen 1-2, 1-3, 1-4 berechnest, brauchst du auch drei alphas, und nicht nur eins. Sonst liegen die drei Punkte 2, 3 und 4 auf einer Linie mit dem Mittelpunkt, und das ist ja keine allgemeine Lage!

EDIT: Das ist keine Höllenmaschine, sondern ein schnöder Athlon-XP 2600+. Aber eben kompilierte C-Software, und da schafft man pro Sekunde zig-Millionen Schleifen.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
1000 Simulationslaeufe mit jeweils 100000 Simulationen

 k  Mittelwert  Std.abw.  5%-Quantil   95%-Quantil
11  0.28876     0.00051   0.28794      0.28961
12  0.27594     0.00050   0.27513      0.27677
13  0.26465     0.00047   0.26387      0.26541
14  0.25459     0.00046   0.25384      0.25535
15  0.24557     0.00045   0.24485      0.24632
16  0.23742     0.00042   0.23672      0.23812
17  0.23001     0.00041   0.22935      0.23069
18  0.22324     0.00039   0.22260      0.22389
19  0.21701     0.00038   0.21641      0.21765
20  0.21128     0.00037   0.21071      0.21189

 k  relativ zum mittleren Abstand nur einer Adresse
11  0.3189
12  0.3048
13  0.2923
14  0.2812
15  0.2712
16  0.2622
17  0.2540
18  0.2466
19  0.2397
20  0.2333
well Auf diesen Beitrag antworten »

Jaaaa, Tanzen jetzt bin ich mit meiner Simulation nah an Deinen Ergebissen. Ich wäre wahrscheinlich nie darauf gestossen, dass der Wurm an den Alphas liegt.

Vielen Dank dafür, für die weiteren Sim-Ergebnisse und noch mal für alles andere Hilf- u. Lehrreiche!!!!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »