Benutzer:Phrood/tmp

Beispiel eines zweidimensionalen Hard-core-Punktfeldes. Der Mindestabstand zwischen den Punkten wird durch die einander nicht überlappenden Kreise veranschaulicht; der Durchmesser der Kreise entspricht dem Mindestabstand.

Ein Hard-core-Prozess ist ein stochastischer Punktprozess, bei dem aufeinanderfolgende Ereignisse einen festgelegten Mindestabstand zueinander einhalten. Aus Sicht der stochastischen Geometrie bestehen $n$-dimensionale Punktfelder, die durch Hard-core-Prozesse erzeugt wurden, aus den Mittelpunkten $n$-dimensionaler, sich nicht gegenseitig durchdringender Kugeln mit vorgegebenem Durchmesser.

Je nach der Art und Weise, wie die Punkte erzeugt werden, lassen sich verschiedene Hard-core-Prozesse mit unterschiedlichen Eigenschaften beschreiben. Hard-core-Prozesse werden hauptächlich in der theoretischen Ökologie und Physik der kondensierten Materie zur Modellierung verschiedener Phänomene angewandt. Weitere Anwendungen finden Hard-core-Prozesse in der Computergrafik, wo sie auch als Poisson-disk- oder Blue-noise-Abtastung bezeichnet werden.

Beispiel: Einparkproblem

Ein einfaches Beispiel eines Hard-core-Prozesses ist das „Random car parking problem“ („Problem des zufälligen Einparkens“), das 1958 von Alfréd Rényi beschrieben wurde. Auf der Strecke $[0,1]$ (der Straße) werden nacheinander zufällig Positionen gewählt. Um jede dieser Positionen wird ein Intervall der Länge δ (ein Auto) platziert, sofern es keines der bisher platzierten Intervalle überlappt. Dabei handelt es sich um einen eindimensionalen Hard-core-Prozess, da die Mittelpunkte der Intervalle einen Mindestabstand von δ einhalten. Rényi interessierte sich für den Erwartungswert der Anzahl von Intervallen, die auf diese Weise platziert werden können (siehe unter „Eigenschaften“ für die Lösung).

Die rein zufällige Wahl von Positionen, ohne Einhaltung eines Mindestabstands, wird durch den Poisson-Prozess modelliert. Ein Beispiel für einen Poisson-Prozess ist das Auftreffen von Regentropfen auf dem Boden. Der Poisson-Prozess kann demnach als Hard-core-Prozess mit $\delta =0$ aufgefasst werden.

Oft sind nur vollständige Hard-core-Punktfelder von praktischem Interesse, also Punktfelder, bei denen kein weiterer Punkt mehr in die vorgegebene Fläche hinzugefügt werden kann. Je nach Mindestabstand und je nachdem, wie eng die Punkte zueinander platziert werden, enthält ein vollständiges Hard-core-Punktfeld mehr oder weniger Punkte.

Arten von Hard-core-Prozessen

Grundlegende Methoden

Simple sequential inhibition

Das im vorherigen Abschnitt beschriebene Prozess beim Einparkproblem lässt sich auf zwei und höhere Dimensionen verallgemeinern; er wird in der Statistik im Allgemeinen als Simple sequential inhibition (SSI), in der Physik und Chemie als Random sequential adsorption (RSA), in der Sequenzplanung als On-line packing und in der Computergrafik als Dart throwing bezeichnet. Hierbei werden nach und nach Punkte von einem Poisson-Prozess erzeugt, aber nur jene berücksichtigt, die den Mindestabstand zu allen bisher beibehaltenen Punkten einhalten.

Algorithmisch lässt sich die Erzeugung von SSI-Punktfeldern mit folgendem Pseudocode beschreiben. ξ steht hierbei für eine zufällig generierte reelle Zahl zwischen 0 und 1 (oder, bei mehrdimensionalen Punktfeldern, für Tupel solcher Zufallszahlen).

Punktfeld ← (leer)
Wiederhole n mal
  Kandidat ← ξ
  Für jeden Existierender_Punkt in Punktfeld
    Wenn ||Kandidat - Existierender_Punkt|| < δ
      Nächstes n
  Füge Kandidat zu Punktfeld hinzu

Erster matérnscher Hard-Core-Prozess

Bertil Matérn beschrieb drei Arten von Hard-core-Prozessen, die durch Ausdünnung eines Poisson-Prozesses entstehen, d. h. durch das nachträgliche Löschen bestimmter Punkte, die von einem Poisson-Prozesses erzeugt wurden. Anders als beim im vorherigen Abschnitt beschriebenen SSI-Prozess werden Punkte erst gelöscht, nachdem das vollständige Poisson-Punktfeld erzeugt wurde. Beim ersten matérnschen Prozess werden die vom Poisson-Prozess erzeugten Punkte mit einer zufälligen „Markierung“ versehen. Anschließend werden alle Punkte beibehalten, die innerhalb des Mindestabstands keine Nachbarpunkte mit einer niedrigeren Markierung haben (unabhängig davon, ob die Nachbarpunkte selbst zur Löschung vorgesehen sind oder nicht).

Der Algorithmus zur Erzeugung von Punktfeldern nach dem ersten Matérn-Prozess ist wie folgt:

Punktfeld ← (leer)
Wiederhole n mal
  Punkt ← ξ
  Punkt.Markierung ← ξ
  Füge Punkt zu Punktfeld hinzu

Zu_löschende_Punkte ← (leer)
Für jeden Punkt in Punktfeld
  Für jeden Nachbarpunkt in Punktfeld
    Wenn ||Punkt - Nachbarpunkt|| < δ und Nachbarpunkt.Markierung < Punkt.Markierung
      Füge Punkt zu Zu_löschende_Punkte hinzu
      Nächster Punkt

Für jeden Punkt in Zu_löschende_Punkte
  Lösche Punkt aus Punktfeld

Zweiter matérnscher Hard-Core-Prozess

Der zweite matérnsche Hard-Core-Prozess verfährt wie der erste, anstatt einer zufälligen Markierung wird allerdings jedem Punkt eine „Geburtszeit“ zugewiesen. Es werden die Punkte beibehalten, die innerhalb des Mindestabstands keine vorher erzeugten Nachbarpunkte haben.

Der Algorithmus lautet wie im vorherigen Abschnitt, wobei die vierte Zeile durch Punkt.Markierung ← n ersetzt wird.

Dritter matérnscher Hard-Core-Prozess

Matérn erwähnte kurz einen dritten Prozess, .

Dead leaves model

Dead leaves model („Modell der abgestorbenen Blätter“) oder Non-overlapping germ-grain model („Modell der nicht-überdeckenden Samenkörner)“.

Eigenschaften

Statistische Eigenschaften

Die erwartete Anzahl der Punkte pro Einheitsfläche ist die Intensität des Prozesses. Wenn man sich Kugeln mit Durchmesser δ um die Punkte denkt, so ist der Extremfall die dichteste Kugelpackung mit größtmöglicher Packungsdichte. Die Packungsdichte ist definiert als der Anteil des Raumes, der von den Kugeln eingenommen wird; ihr maximaler Wert beträgt in zwei Dimensionen $\textstyle {\frac {\pi }{2{\sqrt {3}}}}\approx 0{,}91$ und in drei Dimensionen $\textstyle {\frac {\pi }{3{\sqrt {2}}}}\approx 0{,}74$. Die erwartete Packungsdichte eines Prozesses geht aus der Anzahl der Dimensionen und aus der Intensität des Prozesses hervor.

Prozess	Intensität $\lambda$	Produktdichte $g(t)$ für $t>\delta$
SSI
Matérn I	$\alpha \exp(-\pi \alpha \delta ^{2})$	$\alpha ^{2}\exp(-\alpha U(t))$
Matérn II	${\frac {1-\exp(-\pi \alpha \delta ^{2})}{\pi \delta ^{2}}}$	${\frac {2U(t)(1-\exp(-\pi \alpha \delta ^{2})-2\pi \delta ^{2}(1-\exp(-\alpha (t)))}{\pi \delta ^{2}U(t)(U(t)-\pi \delta ^{2})}}$
Matérn III

Literatur

• A. D. Cliff, J. K. Ord: Spatial processes: models & applications, S. 103 f. Pion, London 1981, ISBN 0-85086-081-4
• Peter J. Diggle: Statistical analysis of spatial point patterns, S. 60 ff. Academic Press, London 1983, ISBN 0-12-215850-4
• Janine Illian: Statistical analysis and modelling of spatial point patterns, S. 387–397. Wiley, Chichester 2008, ISBN 978-0-470-01491-2
• Ares Lagae, Philip Dutré: A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum, 27, 1 (März 2008): 114–129, ISSN 0167-7055 (PDF, 910 KB)
• Bertil Matérn: Spatial variation (=Lecture Notes in Statistics 36). Springer, Berlin 1986, ISBN 0-387-96365-0
• Dietrich Stoyan: Simulation and characterization of random systems of hard particles. Image Analysis and Stereology 21 (Dez. 2002): 41–48, ISSN 1580-3139 (PDF, 3,7 MB)
• Dietrich Stoyan, Wilfried S. Kendall, Joseph Mecke: Stochastic geometry and its applications, S. 162–166. Wiley, Chichester 1995, ISBN 0-471-95099-8

Einzelnachweise

[[Kategorie:Stochastischer Prozess] [[Kategorie:Algorithmus (Computergrafik)] [[Kategorie:Algorithmische Geometrie]