mini|hochkant=1.3|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 -dimensionale Punktfelder, die durch Hard-core-Prozesse erzeugt wurden, aus den Mittelpunkten -dimensionaler, sich nicht gegenseitig durchdringender Kugeln mit vorgegebenem Durchmesser. Siehe auch Modell harter Kugeln.
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.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, Auf der Strecke (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.
500px
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 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.
Verschiedene Hard-core-Prozesse und ihre Simulation 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 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.Bertil Matérn: Spatial variation. Meddelanden från Statens Skogsförsöksanstalt 49 (1960): 1–144, . Siehe auch Bertil Matérn: Spatial variation (=Lecture Notes in Statistics 36), S. 47 ff. Springer, Berlin 1986, ISBN 3-540-96365-0 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.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, (PDF, 320 kB)
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.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) 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 die gesamte Fläche abgedeckt ist.Wilfrid S. Kendall, Elke Thönnes: Perfect simulation in stochastic geometry. Pattern Recognition 32 (1999): 1569–1586, (ps.gz, 420 kB) Der Prozess lässt sich auf andere Dimensionen übertragen.
Simulation von Kugelpackungen In der Festkörperphysik wurden besondere Hard-core-Prozesse entwickelt, um dichte zufällige Kugelpackungen zu simulieren und zu untersuchen. Üblicherweise werden zur Simulation dieser Punktprozesse horizontal periodische Randbedingungen gewählt.
Sedimentationsalgorithmus Jodrey und Torys Sedimentationsalgorithmus simuliert Kugelpackungen durch das sukzessive Fallenlassen von Kugeln in einen Container.W. Steven Jodrey, Elmer M. Tory: Simulation of random packing of spheres. Simulation 32, 1 (Jan. 1979): 1–12, Ausgangspunkt ist eine initiale Kugelschicht („Startkombination“) am Boden des Containers. Es werden dann nach und nach Kugeln hinzugefügt, die aufgrund der Gravitation nach unten fallen und dann, ohne abzuprallen, an den existierenden Kugeln entlangrollen, bis sie an einer stabilen Position zum Liegen kommen. Als stabil gilt eine Position, wenn die Kugel mindestens drei Nachbarn (oder den Boden und zwei Nachbarn) berührt. Falls nach einer festgelegten Zeit keine stabile Position für eine Kugel gefunden werden kann, wird der Versuch mit einer neuen Kugel wiederholt. Der Prozess wiederholt sich so lange, bis der Container gefüllt ist.
Die mit dem Sedimentationsalgorithmus erreichbare Dichte ist geringer als bei natürlichen Kugelpackungen; die maximale Packungsdichte des Algorithmus beträgt ungefähr 0,58.William M. Visscher, M. Bolsterli: Random Packing of Equal and Unequal Spheres in Two and Three Dimensions. Nature 239 (27. Okt. 1972): 504–507, . Zitiert in Antje Elsner: Computergestützte Simulation und Analyse zufälliger dichter Kugelpackungen, S. 21. Dissertation, Technische Universität Bergakademie Freiberg 2009 (PDF, 6,6 MB) Das liegt daran, dass nicht die optimale Position für die Kugeln bestimmt wird, sondern jeweils die erste akzeptiert wird. Es ist außerdem eine Unregelmäßigkeit in der Dichteverteilung entlang der vertikalen Achse feststellbar. Wegen dieser unerwünschten Eigenschaften wird der Sedimentationsalgorithmus meist nicht mehr zur Simulation dichter Kugelpackungen verwendet.
Collective-rearrangement-Algorithmen Bei der Gruppe der Collective-rearrangement-Algorithmen bleibt die vorgegebene Anzahl der Kugeln konstant. Im Laufe der Simulation werden viele der Kugeln verschoben. Ein bekannter Algorithmus aus dieser Gruppe ist der Force-biased-Algorithmus, der auf einer Idee von Jodrey und Torey basiert.W. S. Jodrey, E. M. Tory: Computer simulation of close random packing of equal spheres. Physical Review A 32 (1985): 2347–2351, Als Ausgangspunkt wird eine Menge von zufällig verteilten, eventuell überlappenden Kugeln im Container gewählt. Nur diese Ausgangskonfiguration ist zufällig, der restliche Algorithmus arbeitet deterministisch. Die Kugeln werden voneinander weg verschoben, so als ob ein abstoßendes Kraftfeld zwischen ihnen wirken würde. Gleichzeitig wird der Radius der Kugeln mit einem Faktor kleiner als 1 multipliziert. Dieser Vorgang wiederholt sich so lange, bis die Kugeln einander nicht mehr überlappen.