New path integral simulation algorithms and their application to creep in the quantum sine-Gordon chain

A path integral simulation algorithm which includes a higher-order Trotter approximation (HOA)is analyzed and compared to an approach which includes the correct quantum mechanical pair interaction (effective Propagator (EPr)). It is found that the HOA algorithmconverges to the quantum limit with increasing Trotter number P as P^{-4}, while the EPr algorithm converges as P^{-2}.The convergence rate of the HOA algorithm is analyzed for various physical systemssuch as a harmonic chain,a particle in a double-well potential, gaseous argon, gaseous helium and crystalline argon. A new expression for the estimator for the pair correlation function in the HOA algorithm is derived. A new path integral algorithm, the hybrid algorithm, is developed.It combines an exact treatment of the quadratic part of the Hamiltonian and thehigher-order Trotter expansion techniques.For the discrete quantum sine-Gordon chain (DQSGC), it is shown that this algorithm works more efficiently than all other improved path integral algorithms discussed in this work. The new simulation techniques developed in this work allow the analysis of theDQSGC and disordered model systems in the highly quantum mechanical regime using path integral molecular dynamics (PIMD)and adiabatic centroid path integral molecular dynamics (ACPIMD).The ground state phonon dispersion relation is calculated for the DQSGC by the ACPIMD method.It is found that the excitation gap at zero wave vector is reduced by quantum fluctuations. Two different phases exist: One phase with a finite excitation gap at zero wave vector, and a gapless phase where the excitation gap vanishes.The reaction of the DQSGC to an external driving force is analyzed at T=0.In the gapless phase the system creeps if a small force is applied, and in the phase with a gap the system is pinned. At a critical force, the systems undergo a depinning transition in both phases and flow is induced. The analysis of the DQSGC is extended to models with disordered substrate potentials. Three different cases are analyzed: Disordered substrate potentials with roughness exponent H=0, H=1/2,and a model with disordered bond length. For all models, the ground state phonon dispersion relation is calculated.

Die Faktorisierungsmethode für die elektrische Impedanztomographie im Halbraum

In der vorliegenden Arbeit wird die Faktorisierungsmethode zur Erkennung von Inhomogenitäten der Leitfähigkeit in der elektrischen Impedanztomographie auf unbeschränkten Gebieten - speziell der Halbebene bzw. dem Halbraum - untersucht. Als Lösungsräume für das direkte Problem, d.h. die Bestimmung des elektrischen Potentials zu vorgegebener Leitfähigkeit und zu vorgegebenem Randstrom, führen wir gewichtete Sobolev-Räume ein. In diesen wird die Existenz von schwachen Lösungen des direkten Problems gezeigt und die Gültigkeit einer Integraldarstellung für die Lösung der Laplace-Gleichung, die man bei homogener Leitfähigkeit erhält, bewiesen. Mittels der Faktorisierungsmethode geben wir eine explizite Charakterisierung von Einschlüssen an, die gegenüber dem Hintergrund eine sprunghaft erhöhte oder erniedrigte Leitfähigkeit haben. Damit ist zugleich für diese Klasse von Leitfähigkeiten die eindeutige Rekonstruierbarkeit der Einschlüsse bei Kenntnis der lokalen Neumann-Dirichlet-Abbildung gezeigt. Die mittels der Faktorisierungsmethode erhaltene Charakterisierung der Einschlüsse haben wir in ein numerisches Verfahren umgesetzt und sowohl im zwei- als auch im dreidimensionalen Fall mit simulierten, teilweise gestörten Daten getestet. Im Gegensatz zu anderen bekannten Rekonstruktionsverfahren benötigt das hier vorgestellte keine Vorabinformation über Anzahl und Form der Einschlüsse und hat als nicht-iteratives Verfahren einen vergleichsweise geringen Rechenaufwand.

Untersuchung zur Bestimmung quantitativer Parameter der Lungenventilation mittels CT und MRT

Die zuverlässige Berechnung von quantitativen Parametern der Lungenventilation ist für ein Verständnis des Verhaltens der Lunge und insbesondere für die Diagnostik von Lungenerkrankungen von großer Bedeutung. Nur durch quantitative Parameter sind verlässliche und reproduzierbare diagnostische Aussagen über den Gesundheitszustand der Lunge möglich. Im Rahmen dieser Arbeit wurden neue quantitative Verfahren zur Erfassung der Lungenventilation basierend auf der dynamischen Computer- (CT) und Magnetresonanztomographie (MRT) entwickelt. Im ersten Teil dieser Arbeit wurde die Frage untersucht, ob das Aufblähen der Lunge in gesunden Schweinelungen und Lungen mit Akutem Lungenversagen (ARDS) durch einzelne, diskrete Zeitkonstanten beschrieben werden kann, oder ob kontinuierliche Verteilungen von Zeitkonstanten die Realität besser beschreiben. Hierzu wurden Serien dynamischer CT-Aufnahmen während definierter Beatmungsmanöver (Drucksprünge) aufgenommen und anschließend aus den Messdaten mittels inverser Laplace-Transformation die zugehörigen Verteilungen der Zeitkonstanten berechnet. Um die Qualität der Ergebnisse zu analysieren, wurde der Algorithmus im Rahmen von Simulationsrechnungen systematisch untersucht und anschließend in-vivo an gesunden und ARDS-Schweinelungen eingesetzt. Während in den gesunden Lungen mono- und biexponentielle Verteilungen bestimmt wurden, waren in den ARDS-Lungen Verteilungen um zwei dominante Zeitkonstanten notwendig, um die gemessenen Daten auf der Basis des verwendeten Modells verlässlich zu beschreiben. Es wurden sowohl diskrete als auch kontinuierliche Verteilungen gefunden. Die CT liefert Informationen über das solide Lungengewebe, während die MRT von hyperpolarisiertem 3He in der Lage ist, direkt das eingeatmete Gas abzubilden. Im zweiten Teil der Arbeit wurde zeitlich hochaufgelöst das Einströmen eines 3He-Bolus in die Lunge erfasst. Über eine Entfaltungsanalyse wurde anschließend das Einströmverhalten unter Idealbedingungen (unendlich kurzer 3He-Bolus), also die Gewebeantwortfunktion, berechnet und so eine Messtechnik-unabhängige Erfassung des Einströmens von 3He in die Lunge ermöglicht. Zentrale Fragestellung war hier, wie schnell das Gas in die Lunge einströmt. Im Rahmen von Simulationsrechnungen wurde das Verhalten eines Entfaltungsalgorithmus (basierend auf B-Spline Repräsentationen) systematisch analysiert. Zusätzlich wurde ein iteratives Entfaltungsverfahren eingesetzt. Aus zeitlich hochaufgelösten Messungen (7ms) an einer gesunden und einer ARDS-Schweinelunge konnte erstmals nachgewiesen werden, dass das Einströmen in-vivo in weniger als 0,1s geschieht. Die Ergebnisse zeigen Zeitkonstanten im Bereich von 4ms–50ms, wobei zwischen der gesunden Lungen und der ARDS-Lunge deutliche Unterschiede beobachtet wurden. Zusammenfassend ermöglichen daher die in dieser Arbeit vorgestellten Algorithmen eine objektivere Bestimmung quantitativer Parameter der Lungenventilation. Dies ist für die eindeutige Beschreibung ventilatorischer Vorgänge in der Lunge und somit für die Lungendiagnostik unerlässlich. Damit stehen quantitative Methoden für die Lungenfunktionsdiagnostik zur Verfügung, deren diagnostische Relevanz im Rahmen wissenschaftlicher und klinischer Studien untersucht werden kann.

Entwicklung und Tests von Algorithmen für die Impedanztomographie

Die Elektrische Impedanztomographie soll als kostengünstige und nebenwirkungsfreie Tomographiemethode in der medizinischen Diagnostik, z. B. in der Mammographie dienen. Mit der EIT läßt sich Krebsgewebe von gesundem Gewebe unterscheiden, da es eine signifikant erhöhte Leitfähigkeit aufweist. Damit kann die EIT als Ergänzung zu den klassischen Diagnoseverfahren dienen. So ist z.B. bei jungen Frauen mit einem dichteren Fettgewebe die Identifizierung eines Mammakarzinoms mit der Röntgentomographie nicht immer möglich. Ziel dieser Arbeit war es, einen Prototypen für die Impedanztomographie zu entwickeln und mögliche Anwendungen zu testen. Der Tomograph ist in Zusammenarbeit mit Dr. K.H.Georgi gebaut worden. Der Tomograph erlaubt es niederohmige, Wechselströme an Elektroden auf der Körperoberfläche einzuspeisen. Die Potentiale können an diesen Elektroden programmierbar vorgegeben werden. Weitere hochohmige Elektroden dienen zur Potentialmessung. Um den Hautwiderstand zu überbrücken, werden Wechselstromfrequenzen von 20-100 kHz eingesetzt. Mit der Möglichkeit der Messung von Strom und Potential auf unterschiedlichen Elektroden kann man das Problem des nur ungenau bekannten Hautwiderstandes umgehen. Prinzipiell ist es mit dem Mainzer EIT System möglich, 100 Messungen in der Sekunde durchzuführen. Auf der Basis von mit dem Mainzer EIT gewonnenen Daten sollten unterschiedliche Rekonstruktionsalgorithmen getestet und weiterentwickelt werden. In der Vergangenheit sind verschiedene Rekonstruktionsalgorithmen für das mathematisch schlecht gestellte EIT Problem betrachtet worden. Sie beruhen im Wesentlichen auf zwei Strategien: Die Linearisierung und iterative Lösung des Problems und Gebietserkennungsmethoden. Die iterativen Verfahren wurden von mir dahingehend modifiziert, dass Leitfähigkeitserhöhungen und Leitfähigkeitserniedrigungen gleichberechtigt behandelt werden können. Für den modifizierten Algorithmus wurden zwei verschiedene Rekonstruktionsalgorithmen programmiert und mit synthetischen Daten getestet. Zum einen die Rekonstruktion über die approximative Inverse, zum anderen eine Rekonstruktion mit einer Diskretisierung. Speziell für die Rekonstruktion mittels Diskretisierung wurde eine Methode entwickelt, mit der zusätzliche Informationen in der Rekonstruktion berücksichtigt werden können, was zu einer Verbesserung der Rekonstruktion beiträgt. Der Gebietserkennungsalgorithmus kann diese Zusatzinformationen liefern. In der Arbeit wurde ein neueres Verfahren für die Gebietserkennung derart modifiziert, dass eine Rekonstruktion auch für getrennte Strom- und Spannungselektroden möglich wurde. Mit Hilfe von Differenzdaten lassen sich ausgezeichnete Rekonstruktionen erzielen. Für die medizinischen Anwendungen sind aber Absolutmessungen nötig, d.h. ohne Leermessung. Der erwartende Effekt einer Inhomogenität in der Leitfähigkeit ist sehr klein und als Differenz zweier grosser Zahlen sehr schwierig zu bestimmen. Die entwickelten Algorithmen kommen auch gut mit Absolutdaten zurecht.

Efficient parallel proximity queries and an application to highly complex motion planning problems with many narrow passages

In vielen Bereichen der industriellen Fertigung, wie zum Beispiel in der Automobilindustrie, wer- den digitale Versuchsmodelle (sog. digital mock-ups) eingesetzt, um die Entwicklung komplexer Maschinen m ̈oglichst gut durch Computersysteme unterstu ̈tzen zu k ̈onnen. Hierbei spielen Be- wegungsplanungsalgorithmen eine wichtige Rolle, um zu gew ̈ahrleisten, dass diese digitalen Pro- totypen auch kollisionsfrei zusammengesetzt werden k ̈onnen. In den letzten Jahrzehnten haben sich hier sampling-basierte Verfahren besonders bew ̈ahrt. Diese erzeugen eine große Anzahl von zuf ̈alligen Lagen fu ̈r das ein-/auszubauende Objekt und verwenden einen Kollisionserken- nungsmechanismus, um die einzelnen Lagen auf Gu ̈ltigkeit zu u ̈berpru ̈fen. Daher spielt die Kollisionserkennung eine wesentliche Rolle beim Design effizienter Bewegungsplanungsalgorith- men. Eine Schwierigkeit fu ̈r diese Klasse von Planern stellen sogenannte “narrow passages” dar, schmale Passagen also, die immer dort auftreten, wo die Bewegungsfreiheit der zu planenden Objekte stark eingeschr ̈ankt ist. An solchen Stellen kann es schwierig sein, eine ausreichende Anzahl von kollisionsfreien Samples zu finden. Es ist dann m ̈oglicherweise n ̈otig, ausgeklu ̈geltere Techniken einzusetzen, um eine gute Performance der Algorithmen zu erreichen.rnDie vorliegende Arbeit gliedert sich in zwei Teile: Im ersten Teil untersuchen wir parallele Kollisionserkennungsalgorithmen. Da wir auf eine Anwendung bei sampling-basierten Bewe- gungsplanern abzielen, w ̈ahlen wir hier eine Problemstellung, bei der wir stets die selben zwei Objekte, aber in einer großen Anzahl von unterschiedlichen Lagen auf Kollision testen. Wir im- plementieren und vergleichen verschiedene Verfahren, die auf Hu ̈llk ̈operhierarchien (BVHs) und hierarchische Grids als Beschleunigungsstrukturen zuru ̈ckgreifen. Alle beschriebenen Verfahren wurden auf mehreren CPU-Kernen parallelisiert. Daru ̈ber hinaus vergleichen wir verschiedene CUDA Kernels zur Durchfu ̈hrung BVH-basierter Kollisionstests auf der GPU. Neben einer un- terschiedlichen Verteilung der Arbeit auf die parallelen GPU Threads untersuchen wir hier die Auswirkung verschiedener Speicherzugriffsmuster auf die Performance der resultierenden Algo- rithmen. Weiter stellen wir eine Reihe von approximativen Kollisionstests vor, die auf den beschriebenen Verfahren basieren. Wenn eine geringere Genauigkeit der Tests tolerierbar ist, kann so eine weitere Verbesserung der Performance erzielt werden.rnIm zweiten Teil der Arbeit beschreiben wir einen von uns entworfenen parallelen, sampling- basierten Bewegungsplaner zur Behandlung hochkomplexer Probleme mit mehreren “narrow passages”. Das Verfahren arbeitet in zwei Phasen. Die grundlegende Idee ist hierbei, in der er- sten Planungsphase konzeptionell kleinere Fehler zuzulassen, um die Planungseffizienz zu erh ̈ohen und den resultierenden Pfad dann in einer zweiten Phase zu reparieren. Der hierzu in Phase I eingesetzte Planer basiert auf sogenannten Expansive Space Trees. Zus ̈atzlich haben wir den Planer mit einer Freidru ̈ckoperation ausgestattet, die es erlaubt, kleinere Kollisionen aufzul ̈osen und so die Effizienz in Bereichen mit eingeschr ̈ankter Bewegungsfreiheit zu erh ̈ohen. Optional erlaubt unsere Implementierung den Einsatz von approximativen Kollisionstests. Dies setzt die Genauigkeit der ersten Planungsphase weiter herab, fu ̈hrt aber auch zu einer weiteren Perfor- mancesteigerung. Die aus Phase I resultierenden Bewegungspfade sind dann unter Umst ̈anden nicht komplett kollisionsfrei. Um diese Pfade zu reparieren, haben wir einen neuartigen Pla- nungsalgorithmus entworfen, der lokal beschr ̈ankt auf eine kleine Umgebung um den bestehenden Pfad einen neuen, kollisionsfreien Bewegungspfad plant.rnWir haben den beschriebenen Algorithmus mit einer Klasse von neuen, schwierigen Metall- Puzzlen getestet, die zum Teil mehrere “narrow passages” aufweisen. Unseres Wissens nach ist eine Sammlung vergleichbar komplexer Benchmarks nicht ̈offentlich zug ̈anglich und wir fan- den auch keine Beschreibung von vergleichbar komplexen Benchmarks in der Motion-Planning Literatur.

Software tools and efficient algorithms for the feature detection, feature tracking, event localization, and visualization of large sets of atmospheric data

Data sets describing the state of the earth's atmosphere are of great importance in the atmospheric sciences. Over the last decades, the quality and sheer amount of the available data increased significantly, resulting in a rising demand for new tools capable of handling and analysing these large, multidimensional sets of atmospheric data. The interdisciplinary work presented in this thesis covers the development and the application of practical software tools and efficient algorithms from the field of computer science, aiming at the goal of enabling atmospheric scientists to analyse and to gain new insights from these large data sets. For this purpose, our tools combine novel techniques with well-established methods from different areas such as scientific visualization and data segmentation. In this thesis, three practical tools are presented. Two of these tools are software systems (Insight and IWAL) for different types of processing and interactive visualization of data, the third tool is an efficient algorithm for data segmentation implemented as part of Insight.Insight is a toolkit for the interactive, three-dimensional visualization and processing of large sets of atmospheric data, originally developed as a testing environment for the novel segmentation algorithm. It provides a dynamic system for combining at runtime data from different sources, a variety of different data processing algorithms, and several visualization techniques. Its modular architecture and flexible scripting support led to additional applications of the software, from which two examples are presented: the usage of Insight as a WMS (web map service) server, and the automatic production of a sequence of images for the visualization of cyclone simulations. The core application of Insight is the provision of the novel segmentation algorithm for the efficient detection and tracking of 3D features in large sets of atmospheric data, as well as for the precise localization of the occurring genesis, lysis, merging and splitting events. Data segmentation usually leads to a significant reduction of the size of the considered data. This enables a practical visualization of the data, statistical analyses of the features and their events, and the manual or automatic detection of interesting situations for subsequent detailed investigation. The concepts of the novel algorithm, its technical realization, and several extensions for avoiding under- and over-segmentation are discussed. As example applications, this thesis covers the setup and the results of the segmentation of upper-tropospheric jet streams and cyclones as full 3D objects. Finally, IWAL is presented, which is a web application for providing an easy interactive access to meteorological data visualizations, primarily aimed at students. As a web application, the needs to retrieve all input data sets and to install and handle complex visualization tools on a local machine are avoided. The main challenge in the provision of customizable visualizations to large numbers of simultaneous users was to find an acceptable trade-off between the available visualization options and the performance of the application. Besides the implementational details, benchmarks and the results of a user survey are presented.

Novel algorithms for electronic structure based molecular dynamics with linear system-size scaling

Die vorliegende Arbeit behandelt die Entwicklung und Verbesserung von linear skalierenden Algorithmen für Elektronenstruktur basierte Molekulardynamik. Molekulardynamik ist eine Methode zur Computersimulation des komplexen Zusammenspiels zwischen Atomen und Molekülen bei endlicher Temperatur. Ein entscheidender Vorteil dieser Methode ist ihre hohe Genauigkeit und Vorhersagekraft. Allerdings verhindert der Rechenaufwand, welcher grundsätzlich kubisch mit der Anzahl der Atome skaliert, die Anwendung auf große Systeme und lange Zeitskalen. Ausgehend von einem neuen Formalismus, basierend auf dem großkanonischen Potential und einer Faktorisierung der Dichtematrix, wird die Diagonalisierung der entsprechenden Hamiltonmatrix vermieden. Dieser nutzt aus, dass die Hamilton- und die Dichtematrix aufgrund von Lokalisierung dünn besetzt sind. Das reduziert den Rechenaufwand so, dass er linear mit der Systemgröße skaliert. Um seine Effizienz zu demonstrieren, wird der daraus entstehende Algorithmus auf ein System mit flüssigem Methan angewandt, das extremem Druck (etwa 100 GPa) und extremer Temperatur (2000 - 8000 K) ausgesetzt ist. In der Simulation dissoziiert Methan bei Temperaturen oberhalb von 4000 K. Die Bildung von sp²-gebundenem polymerischen Kohlenstoff wird beobachtet. Die Simulationen liefern keinen Hinweis auf die Entstehung von Diamant und wirken sich daher auf die bisherigen Planetenmodelle von Neptun und Uranus aus. Da das Umgehen der Diagonalisierung der Hamiltonmatrix die Inversion von Matrizen mit sich bringt, wird zusätzlich das Problem behandelt, eine (inverse) p-te Wurzel einer gegebenen Matrix zu berechnen. Dies resultiert in einer neuen Formel für symmetrisch positiv definite Matrizen. Sie verallgemeinert die Newton-Schulz Iteration, Altmans Formel für beschränkte und nicht singuläre Operatoren und Newtons Methode zur Berechnung von Nullstellen von Funktionen. Der Nachweis wird erbracht, dass die Konvergenzordnung immer mindestens quadratisch ist und adaptives Anpassen eines Parameters q in allen Fällen zu besseren Ergebnissen führt.

Efficient algorithms for NLO QCD event generators

In this thesis we present techniques that can be used to speed up the calculation of perturbative matrix elements for observables with many legs ($n = 3, 4, 5, 6, 7, ldots$). We investigate several ways to achieve this, including the use of Monte Carlo methods, the leading-color approximation, numerically less precise but faster operations, and SSE-vectorization. An important idea is the use of enquote{random polarizations} for which we derive subtraction terms for the real corrections in next-to-leading order calculations. We present the effectiveness of all these methods in the context of electron-positron scattering to $n$ jets, $n$ ranging from two to seven.

Dynamic distance analysis : new geometric data structures and algorithms for the real-time calculation of tolerance violating regions in the digital mockup process

In vielen Industriezweigen, zum Beispiel in der Automobilindustrie, werden Digitale Versuchsmodelle (Digital MockUps) eingesetzt, um die Konstruktion und die Funktion eines Produkts am virtuellen Prototypen zu überprüfen. Ein Anwendungsfall ist dabei die Überprüfung von Sicherheitsabständen einzelner Bauteile, die sogenannte Abstandsanalyse. Ingenieure ermitteln dabei für bestimmte Bauteile, ob diese in ihrer Ruhelage sowie während einer Bewegung einen vorgegeben Sicherheitsabstand zu den umgebenden Bauteilen einhalten. Unterschreiten Bauteile den Sicherheitsabstand, so muss deren Form oder Lage verändert werden. Dazu ist es wichtig, die Bereiche der Bauteile, welche den Sicherhabstand verletzen, genau zu kennen. rnrnIn dieser Arbeit präsentieren wir eine Lösung zur Echtzeitberechnung aller den Sicherheitsabstand unterschreitenden Bereiche zwischen zwei geometrischen Objekten. Die Objekte sind dabei jeweils als Menge von Primitiven (z.B. Dreiecken) gegeben. Für jeden Zeitpunkt, in dem eine Transformation auf eines der Objekte angewendet wird, berechnen wir die Menge aller den Sicherheitsabstand unterschreitenden Primitive und bezeichnen diese als die Menge aller toleranzverletzenden Primitive. Wir präsentieren in dieser Arbeit eine ganzheitliche Lösung, welche sich in die folgenden drei großen Themengebiete unterteilen lässt.rnrnIm ersten Teil dieser Arbeit untersuchen wir Algorithmen, die für zwei Dreiecke überprüfen, ob diese toleranzverletzend sind. Hierfür präsentieren wir verschiedene Ansätze für Dreiecks-Dreiecks Toleranztests und zeigen, dass spezielle Toleranztests deutlich performanter sind als bisher verwendete Abstandsberechnungen. Im Fokus unserer Arbeit steht dabei die Entwicklung eines neuartigen Toleranztests, welcher im Dualraum arbeitet. In all unseren Benchmarks zur Berechnung aller toleranzverletzenden Primitive beweist sich unser Ansatz im dualen Raum immer als der Performanteste.rnrnDer zweite Teil dieser Arbeit befasst sich mit Datenstrukturen und Algorithmen zur Echtzeitberechnung aller toleranzverletzenden Primitive zwischen zwei geometrischen Objekten. Wir entwickeln eine kombinierte Datenstruktur, die sich aus einer flachen hierarchischen Datenstruktur und mehreren Uniform Grids zusammensetzt. Um effiziente Laufzeiten zu gewährleisten ist es vor allem wichtig, den geforderten Sicherheitsabstand sinnvoll im Design der Datenstrukturen und der Anfragealgorithmen zu beachten. Wir präsentieren hierzu Lösungen, die die Menge der zu testenden Paare von Primitiven schnell bestimmen. Darüber hinaus entwickeln wir Strategien, wie Primitive als toleranzverletzend erkannt werden können, ohne einen aufwändigen Primitiv-Primitiv Toleranztest zu berechnen. In unseren Benchmarks zeigen wir, dass wir mit unseren Lösungen in der Lage sind, in Echtzeit alle toleranzverletzenden Primitive zwischen zwei komplexen geometrischen Objekten, bestehend aus jeweils vielen hunderttausend Primitiven, zu berechnen. rnrnIm dritten Teil präsentieren wir eine neuartige, speicheroptimierte Datenstruktur zur Verwaltung der Zellinhalte der zuvor verwendeten Uniform Grids. Wir bezeichnen diese Datenstruktur als Shrubs. Bisherige Ansätze zur Speicheroptimierung von Uniform Grids beziehen sich vor allem auf Hashing Methoden. Diese reduzieren aber nicht den Speicherverbrauch der Zellinhalte. In unserem Anwendungsfall haben benachbarte Zellen oft ähnliche Inhalte. Unser Ansatz ist in der Lage, den Speicherbedarf der Zellinhalte eines Uniform Grids, basierend auf den redundanten Zellinhalten, verlustlos auf ein fünftel der bisherigen Größe zu komprimieren und zur Laufzeit zu dekomprimieren.rnrnAbschießend zeigen wir, wie unsere Lösung zur Berechnung aller toleranzverletzenden Primitive Anwendung in der Praxis finden kann. Neben der reinen Abstandsanalyse zeigen wir Anwendungen für verschiedene Problemstellungen der Pfadplanung.