Hard-core-Prozess

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 hauptsä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.^[1] 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.

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.

Meist sind nur vollständige Hard-core-Punktfelder von praktischem Interesse, also Punktfelder, bei denen der zur Generierung verwendete Hard-core-Prozess beendet ist und kein weiterer Punkt mehr in die vorgegebene Fläche hinzugefügt werden kann. Je nach Mindestabstand und je nachdem, wie eng ein Prozess die Punkte platziert, enthält ein vollständiges Hard-core-Punktfeld mehr oder weniger Punkte. Rényi interessierte sich für den Erwartungswert der Anzahl von Intervallen, die durch zufälliges Einparken platziert werden können.

Verchiedene Hard-core-Prozesse und ihre Simulation

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 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.^[2] 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 alle Punkte gelöscht, deren nächstgelegener Nachbarpunkt näher liegt als der Mindestabstand. Falls mehrere Punkte zu nahe beieinander liegen, so werden sie alle gelöscht.

Der Algorithmus zur Erzeugung von Punktfeldern nach dem ersten matérnschen Prozess ist wie folgt:

Punktfeld ← (leer)
Wiederhole n mal
  Punkt ← ξ
  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|| < δ
      Wenn Punkt nicht in Zu_löschende_Punkte vorhanden
        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 Prozess

Beim zweiten matérnschen Prozess werden die vom Poisson-Prozess erzeugten Punkte mit einer aufsteigenden „Markierung“ versehen. Anschließend werden alle Punkte beibehalten, die innerhalb des Mindestabstands keine vorher erzeugten Nachbarpunkte (mit einer niedrigeren Markierung) haben.

Der Algorithmus für den zweiten matérnschen Prozess lautet folgendermaßen:

Punktfeld ← (leer)
Für jedes k von 1 bis n
  Punkt ← ξ
  Punkt.Markierung ← k
  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
      Wenn Punkt nicht in Zu_löschende_Punkte vorhanden
        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

Dritter matérnscher Prozess

Matérn erwähnte kurz einen dritten Prozess, der wie der zweite beginnt. Anschließend wird der gleiche Prozess mit den Punkten des Poisson-Prozesses, die keine Nachbarpunkte der bisher ausgewählten Punkte sind, so lange wiederholt, bis keine neuen Punkte mehr ausgewählt werden können. Der Algorithmus lautet wie folgt:

Punktfeld ← (leer)
Kandidaten ← (leer)
Für jedes k von 1 bis n
  Punkt ← ξ
  Punkt.Markierung ← k
  Füge Punkt zu Kandidaten hinzu

NeuePunkte = Wahr
Wiederhole solange NeuePunkte
  NeuePunkte = Falsch
  Für jeden Punkt in Kandidaten
    Für jeden Nachbarpunkt in Kandidaten
      Wenn ||Punkt - Nachbarpunkt|| < δ und Nachbarpunkt.Markierung < Punkt.Markierung
        Nächster Punkt
    Füge Punkt zu Punktfeld hinzu
    NeuePunkte = Wahr

  Zu_löschende_Punkte ← (leer)
  Für jeden Kandidat in Kandidaten
    Für jeden Punkt in Punktfeld
      Wenn ||Punkt - Kandidat|| < δ
        Wenn Punkt nicht in Zu_löschende_Punkte vorhanden
          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 Kandidaten

Es wurde ein effizienterer Algorithmus zur Simulation von Matérn-III-Punktfeldern beschrieben.^[3]

Dead leaves model

Ein weiterer Hard-core-Prozess ist das Dead leaves model („Modell der abgestorbenen Blätter“), auch Non-overlapping germ-grain model („Modell der nicht-überdeckenden Samenkörner)“ genannt.^[4] Bei diesem Prozess werden Kreise mit Durchmesser δ zufällig in der Ebene platziert, wobei sie vorhandene Kreise überdecken können. Das Hard-core-Punktfeld besteht aus den Mittelpunkten der nicht überdeckten Kreise (der oberen Schicht), nachdem unendlich viele Kreise hinzugefügt wurden. In endlicher Zeit simulieren lässt sich der Prozess, indem neue Kreise nicht über, sondern unter die vorhandenen Kreise platziert werden und der Vorgang abgebrochen wird, sobald neue Kreise die Ebene nicht sichtbar verändern.^[5] Der Prozess lässt sich auf andere Dimensionen übertragen.

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)
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, Joseph Mecke: Stochastische Geometrie: eine Einführung, S. 87–90. Akademie-Verlag, Berlin 1983, ISSN 0084-098X
Dietrich Stoyan, Wilfried S. Kendall, Joseph Mecke: Stochastic geometry and its applications, S. 162–166. Wiley, Chichester 1995, ISBN 0-471-95099-8

Einzelnachweise

↑ Alfréd Rényi: On a one-dimensional problem concerning random space-filling. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 3 (1958): 109–127, ISSN 0541-9514
↑ Bertil Matérn: Spatial variation. Meddelanden från Statens Skogsförsöksanstalt 49 (1960): 1–144, ISSN 0369-2167. Siehe auch Bertil Matérn: Spatial variation (=Lecture Notes in Statistics 36), S. 47 ff. Springer, Berlin 1986, ISBN 3-540-96365-0
↑ Jesper Møller, Mark L. Huber, Robert L. Wolpert: Perfect simulation and moment properties for the Matérn type III process. Stochastic Processes and their Applications 120, 11 (Nov. 2010): 2142–2158, ISSN 0304-4149 (PDF, 320 KB)
↑ Georges Matheron: Schéma booléen séquentiel de partition aléatoire. Note géostatistique N° 89, Centre de Morphologie Mathématique, École des Mines de Paris, Fontainebleau 1968 (PDF, 550 KB)
↑ Wilfrid S. Kendall, Elke Thönnes: Perfect simulation in stochastic geometry. Pattern Recognition 32 (1999): 1569–1586, ISSN 0031-3203 (ps.gz, 420 KB)

[1] Alfréd Rényi: On a one-dimensional problem concerning random space-filling. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 3 (1958): 109–127, ISSN 0541-9514

[2] Bertil Matérn: Spatial variation. Meddelanden från Statens Skogsförsöksanstalt 49 (1960): 1–144, ISSN 0369-2167. Siehe auch Bertil Matérn: Spatial variation (=Lecture Notes in Statistics 36), S. 47 ff. Springer, Berlin 1986, ISBN 3-540-96365-0

[3] Jesper Møller, Mark L. Huber, Robert L. Wolpert: Perfect simulation and moment properties for the Matérn type III process. Stochastic Processes and their Applications 120, 11 (Nov. 2010): 2142–2158, ISSN 0304-4149 (PDF, 320 KB)

[4] Georges Matheron: Schéma booléen séquentiel de partition aléatoire. Note géostatistique N° 89, Centre de Morphologie Mathématique, École des Mines de Paris, Fontainebleau 1968 (PDF, 550 KB)

[5] Wilfrid S. Kendall, Elke Thönnes: Perfect simulation in stochastic geometry. Pattern Recognition 32 (1999): 1569–1586, ISSN 0031-3203 (ps.gz, 420 KB)

[1]

[2]

[3]

[4]

[5]