Multithread parallelization of lepp-bisection algorithms

[EN]Longest edge (nested) algorithms for triangulation refinement in two dimensions are able to produce hierarchies of quality and nested irregular triangulations as needed both for adaptive finite element methods and for multigrid methods. They can be formulated in terms of the longest edge propagation path (Lepp) and terminal edge concepts, to refine the target triangles and some related neighbors. We discuss a parallel multithread algorithm, where every thread is in charge of refining a triangle t and its associated Lepp neighbors. The thread manages a changing Lepp(t) (ordered set of increasing triangles) both to find a last longest (terminal) edge and to refine the pair of triangles sharing this edge...

Solar radiation estimation using a numerical model

[EN]A solar radiation numerical model is presented. It is intented to be useful for different purposes like the evaluation of the suitability of possible locations for solar power stations. This model allows the user to evaluate the radiation values in any location easily, and estimate the solar power generation taking into account not only the radiation level, but also the terrain surface conditions considering the cast shadows. The solar radiation model is implemented taking into account the terrain surface using 2-D adaptive meshes of triangles, which are constructed using a refinement/derefinement procedure in accordance with the variations of terrain surface and albedo...

A new predictive solar radiation numerical model

[EN]A predictive solar radiation numerical model is presented. Starting from the works of, a solar radiation numerical model is developed considering the terrain surface through 2-D adaptive meshes of triangles which are constructed using a refinement/derefinement procedure in accordance with the variations of terrain surface and albedo. The effect of shadows is considered in each time step. Solar radiation is first computed for clear-sky (CS) conditions and then, real-sky values are computed daily in terms of the CS index computed using all the observational data which are available for each day at several points of the studied zone…

Enhanced Mixed Integer Programming Techniques and Routing Problems

Mixed integer programming is up today one of the most widely used techniques for dealing with hard optimization problems. On the one side, many practical optimization problems arising from real-world applications (such as, e.g., scheduling, project planning, transportation, telecommunications, economics and finance, timetabling, etc) can be easily and effectively formulated as Mixed Integer linear Programs (MIPs). On the other hand, 50 and more years of intensive research has dramatically improved on the capability of the current generation of MIP solvers to tackle hard problems in practice. However, many questions are still open and not fully understood, and the mixed integer programming community is still more than active in trying to answer some of these questions. As a consequence, a huge number of papers are continuously developed and new intriguing questions arise every year. When dealing with MIPs, we have to distinguish between two different scenarios. The first one happens when we are asked to handle a general MIP and we cannot assume any special structure for the given problem. In this case, a Linear Programming (LP) relaxation and some integrality requirements are all we have for tackling the problem, and we are ``forced" to use some general purpose techniques. The second one happens when mixed integer programming is used to address a somehow structured problem. In this context, polyhedral analysis and other theoretical and practical considerations are typically exploited to devise some special purpose techniques. This thesis tries to give some insights in both the above mentioned situations. The first part of the work is focused on general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. Chapter 1 presents a quick overview of the main ingredients of a branch-and-cut algorithm, while Chapter 2 recalls some results from the literature in the context of disjunctive cuts and their connections with Gomory mixed integer cuts. Chapter 3 presents a theoretical and computational investigation of disjunctive cuts. In particular, we analyze the connections between different normalization conditions (i.e., conditions to truncate the cone associated with disjunctive cutting planes) and other crucial aspects as cut rank, cut density and cut strength. We give a theoretical characterization of weak rays of the disjunctive cone that lead to dominated cuts, and propose a practical method to possibly strengthen those cuts arising from such weak extremal solution. Further, we point out how redundant constraints can affect the quality of the generated disjunctive cuts, and discuss possible ways to cope with them. Finally, Chapter 4 presents some preliminary ideas in the context of multiple-row cuts. Very recently, a series of papers have brought the attention to the possibility of generating cuts using more than one row of the simplex tableau at a time. Several interesting theoretical results have been presented in this direction, often revisiting and recalling other important results discovered more than 40 years ago. However, is not clear at all how these results can be exploited in practice. As stated, the chapter is a still work-in-progress and simply presents a possible way for generating two-row cuts from the simplex tableau arising from lattice-free triangles and some preliminary computational results. The second part of the thesis is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications. Chapters 5 and 6 present an integer linear programming local search algorithm for Vehicle Routing Problems (VRPs). The overall procedure follows a general destroy-and-repair paradigm (i.e., the current solution is first randomly destroyed and then repaired in the attempt of finding a new improved solution) where a class of exponential neighborhoods are iteratively explored by heuristically solving an integer programming formulation through a general purpose MIP solver. Chapters 7 and 8 deal with exact branch-and-cut methods. Chapter 7 presents an extended formulation for the Traveling Salesman Problem with Time Windows (TSPTW), a generalization of the well known TSP where each node must be visited within a given time window. The polyhedral approaches proposed for this problem in the literature typically follow the one which has been proven to be extremely effective in the classical TSP context. Here we present an overall (quite) general idea which is based on a relaxed discretization of time windows. Such an idea leads to a stronger formulation and to stronger valid inequalities which are then separated within the classical branch-and-cut framework. Finally, Chapter 8 addresses the branch-and-cut in the context of Generalized Minimum Spanning Tree Problems (GMSTPs) (i.e., a class of NP-hard generalizations of the classical minimum spanning tree problem). In this chapter, we show how some basic ideas (and, in particular, the usage of general purpose cutting planes) can be useful to improve on branch-and-cut methods proposed in the literature.

Fluidodinamica biomedica computazionale del flusso sanguigno in presenza di affezioni strumentali e/o patologiche

La tesi di Dottorato studia il flusso sanguigno tramite un codice agli elementi finiti (COMSOL Multiphysics). Nell’arteria è presente un catetere Doppler (in posizione concentrica o decentrata rispetto all’asse di simmetria) o di stenosi di varia forma ed estensione. Le arterie sono solidi cilindrici rigidi, elastici o iperelastici. Le arterie hanno diametri di 6 mm, 5 mm, 4 mm e 2 mm. Il flusso ematico è in regime laminare stazionario e transitorio, ed il sangue è un fluido non-Newtoniano di Casson, modificato secondo la formulazione di Gonzales & Moraga. Le analisi numeriche sono realizzate in domini tridimensionali e bidimensionali, in quest’ultimo caso analizzando l’interazione fluido-strutturale. Nei casi tridimensionali, le arterie (simulazioni fluidodinamiche) sono infinitamente rigide: ricavato il campo di pressione si procede quindi all’analisi strutturale, per determinare le variazioni di sezione e la permanenza del disturbo sul flusso. La portata sanguigna è determinata nei casi tridimensionali con catetere individuando tre valori (massimo, minimo e medio); mentre per i casi 2D e tridimensionali con arterie stenotiche la legge di pressione riproduce l’impulso ematico. La mesh è triangolare (2D) o tetraedrica (3D), infittita alla parete ed a valle dell’ostacolo, per catturare le ricircolazioni. Alla tesi sono allegate due appendici, che studiano con codici CFD la trasmissione del calore in microcanali e l’ evaporazione di gocce d’acqua in sistemi non confinati. La fluidodinamica nei microcanali è analoga all’emodinamica nei capillari. Il metodo Euleriano-Lagrangiano (simulazioni dell’evaporazione) schematizza la natura mista del sangue. La parte inerente ai microcanali analizza il transitorio a seguito dell’applicazione di un flusso termico variabile nel tempo, variando velocità in ingresso e dimensioni del microcanale. L’indagine sull’evaporazione di gocce è un’analisi parametrica in 3D, che esamina il peso del singolo parametro (temperatura esterna, diametro iniziale, umidità relativa, velocità iniziale, coefficiente di diffusione) per individuare quello che influenza maggiormente il fenomeno.

Spektromikroskopische Analyse von Nukleationsdomänen in epitaktischen Diamantschichten auf Ir,SrTiO 3 und von präsolaren SiC-Meteoritenkörnern

Im Rahmen dieser Arbeit wurden zwei verschiedene Systeme untersucht, deren verbindende Gemeinsamkeit in den verwendeten ortsauflösenden, spektroskopischen Messmethoden der Oberflächenanalytik, wie z.B. abbildendes XPS, Röntgennahkanten-Photoemissionsmikroskopie (XANES-PEEM) und Augerspektroskopie (AES) liegt. Im ersten Teil der Arbeit wurden Diamant-Nukleationsdomänen auf Ir/SrTiO3 untersucht und mit vorherrschenden Modellen aus der Literatur verglichen. Die Nukleationsdomänen, wie sie im Mikrowellen-induzierten CVD Prozess unter Verwendung der BEN Prozedur (bias-enhanced nucleation) entstehen, bilden die „Startschicht“ für ein heteroepitaktisches Wachstum einer hoch orientierten Diamantschicht. Sie entwickeln sich aber unter Bedingungen, unter denen 3D-Diamant abgetragen und weggeätzt wird. Mittels XANES-PEEM Messungen konnte erstmals die lokale Bindungsumgebung des Kohlenstoffs in den Nukleationsdomänen ortsaufgelöst aufgezeigt werden und aus AES Messungen ließ sich die Schichtdicke der Nukleationsdomänen abschätzen. Es zeigte sich, dass die Nukleationsdomänen Bereiche mit etwa 1 nm Dicke darstellen, in denen der Übergang von eine sp2-koordinierte amorphen Kohlenstoff- zu einer Diamantschicht mit hohem sp3 Anteil abläuft. Zur Erklärung des Nukleationsprozesses wurde auf das „Clustermodell“ von Lifshitz et al. zurückgegriffen, welches um einen wesentlichen Aspekt erweitert wurde. Die Stabilität der Nukleationsdomänen gegen die Ätzwirkung des Nukleationsprozesses auf Volumendiamant wird durch eine starke Wechselwirkung zwischen dem Diamant und dem Iridiumsubstrat erklärt, wobei die Dicke von etwa 1 nm als Maß für die Ausdehnung dieses Wechselwirkungsbereichs angesehen wird. Der zweite Teil der Arbeit beschäftigt sich mit der Charakterisierung präsolarer SiC-Körner und darin eingeschlossener Spurenelemente. Neben den Hauptelementen Si und C wurden auch Spinelle wie Chromit (FeCr2O4), Korund (Al2O3) und auch verschiedene Spurenelemente (z. B. Al, Ba und Y) nachgewiesen. Ferner wurden XPS-Linien bei Energien nachgewiesen, welche sich den Seltenen Erden Erbium, Thulium und Dysprosium zuordnen lassen. Aufgrund von Abweichungen zur Literatur bzgl. der ausgeprägten Intensität der XPS-Linien, wurde als alternative Erklärungsmöglichkeit für verschiedene Signale der Nachweis von stark schwefelhaltigen Körnern (z.B. so genannte „Fremdlinge“) mit Aufladungen von mehreren Volt diskutiert. Es zeigt sich, dass abbildendes XPS und XANES-PEEM Methoden zur leistungsfähigen chemischen Charakterisierung von SiC-Körnern und anderer solarer und präsolarer Materie im Größenbereich bis herab zu 100 – 200 nm Durchmesser (z.B. als Grundlage für eine spätere massenspektrometrische Isotopenanalyse)darstellen.

Measurement of the oscillation frequency of B s mesons in the hadronic decay mode B s pi D s (phi pi) X with the D0 detector at the Fermilab Tevatron collider

The standard model (SM) of particle physics is a theory, describing three out of four fundamental forces. In this model the Cabibbo-Kobayashi-Maskawa (CKM) matrix describes the transformation between the mass and weak eigenstates of quarks. The matrix properties can be visualized as triangles in the complex plane. A precise measurement of all triangle parameters can be used to verify the validity of the SM. The least precisely measured parameter of the triangle is related to the CKM element |Vtd|, accessible through the mixing frequency (oscillation) of neutral B mesons, where mixing is the transition of a neutral meson into its anti-particle and vice versa. It is possible to calculate the CKM element |Vtd| and a related element |Vts| by measuring the mass differences Dmd (Dms ) between neutral Bd and bar{Bd} (Bs and bar{Bs}) meson mass eigenstates. This measurement is accomplished by tagging the initial and final state of decaying B mesons and determining their lifetime. Currently the Fermilab Tevatron Collider (providing pbar{p} collisions at sqrt{s}=1.96 TeV) is the only place, where Bs oscillations can be studied. The first selection of the "golden", fully hadronic decay mode Bs->Ds pi(phi pi)X at DØ is presented in this thesis. All data, taken between April 2002 and August 2007 with the DØ detector, corresponding to an integrated luminosity of int{L}dt=2.8/fb is used. The oscillation frequency Dms and the ratio |Vtd|/|Vts| are determined as Dms = (16.6 +0.5-0.4(stat) +0.4-0.3(sys)) 1/ps, |Vtd|/|Vts| = 0.213 +0.004-0.003(exp)pm 0.008(theor). These results are consistent with the standard model expectations and no evidence for new physics is observable.

Studium hochkomplexer atomarer Spektren mittels Methoden der Laserresonanzionisation

In dieser Arbeit wurden umfangreiche laserspektroskopische Studien mit dem Zielrneines verbesserten Verständnisses höchst komplexer Spektren der Lanthanide und Aktinide durchgeführt. Einen Schwerpunkt bildete die Bestimmung bisher nicht oder mit unbefriedigender Genauigkeit bekannter erster Ionisationspotentiale für diese Elemente.rnHierzu wurden drei unterschiedliche experimentelle Methoden eingesetzt. Die Bestimmung des Ionisationspotentiales aus Rydbergserien wurde an den Beispielen Eisen, Mangan und Kobalt mit gemessenen Werten von IPFe = 63737, 6 ± 0, 2stat ± 0, 1syst cm−1, IPMn = 59959, 6 ± 0, 4 cm−1 beziehungsweise IPCo = 63564, 77 ± 0, 12 cm−1 zunächst erfolgreich erprobt. Die bestehenden Literaturwerte konnten in diesen Fällen bestätigt werden und bei Eisen und Kobalt die Genauigkeit etwa um einen Faktor drei bzw. acht verbessert werden. Im Falle der Lanthaniden und Aktiniden jedoch ist die Komplexität der Spektren derart hoch, dass Rydbergserien in einer Vielzahl weiterer Zustände beliebiger Konfiguration nicht oder kaum identifiziert werden können.rnUm dennoch das Ionisationspotential bestimmen zu können, wurde die verzögerte, gepulste Feldionisation wie auch das Verfahren der Isolated Core Excitation am Beispiel des Dysprosiums erprobt. Aus den so identifizierten Rydbergserien konnten Werte von IPFeld = 47899 ± 3 cm−1 beziehungsweise IPICE = 47900, 4 ± 1, 4 cm−1 bestimmt werden. Als komplementärer Ansatz, der auf ein möglichst reichhaltiges Spektrum in der Nähe des Ionisationspotentiales angewiesen ist, wurde zusätzlich die Sattelpunktsmethode erfolgreich eingesetzt. Das Ionisationspotential des Dysprosium wurde damit zu IPDy = 47901, 8±0, 3 cm−1 bestimmt, wobei am Samarium, dessen Ionisationspotential aus der Literatur mit höchster Genauigkeit bekannt ist, bestätigt werden konnte, dassrnauftretende systematische Fehler kleiner als 1 cm−1 sind. Das bisher sehr ungenau bekannte Ionisationspotential des Praseodyms wurde schließlich zu IPPr = 44120, 0 ± 0, 6 cm−1 gemessen. Hiermit wird der bisherige Literaturwert bei einer Verbesserung der Genauigkeit um zwei Größenordnungen um etwa 50 cm−1 nach oben korrigiert. Aus der Systematik der Ionisationspotentiale der Lanthaniden konnte schließlich das Ionisationspotential des radioaktiven Promethiums mit IPPm = 44985 ± 140 cm−1 vorhergesagt werden. Abschließend wurde die Laserresonanzionisation des Elements Protactinium demonstriertrnund das Ionisationspotential erstmals experimentell bestimmt. Ein Wert vonrn49000±110 cm−1 konnte aus dem charakteristischen Verhalten verschiedener Anregungsschemata gefolgert werden. Dieser Wert liegt etwa 1500 cm−1 höher als der bisherige Literaturwert, theoretische Vorhersagen weichen ebenfalls stark ab. Beide Abweichungen können über eine Betrachtung der Systematik der Ionisationspotentiale in der Aktinidenreihe hervorragend verstanden werden.

High precision swept volume approximation with conservative error bounds

In technical design processes in the automotive industry, digital prototypes rapidly gain importance, because they allow for a detection of design errors in early development stages. The technical design process includes the computation of swept volumes for maintainability analysis and clearance checks. The swept volume is very useful, for example, to identify problem areas where a safety distance might not be kept. With the explicit construction of the swept volume an engineer gets evidence on how the shape of components that come too close have to be modified.rnIn this thesis a concept for the approximation of the outer boundary of a swept volume is developed. For safety reasons, it is essential that the approximation is conservative, i.e., that the swept volume is completely enclosed by the approximation. On the other hand, one wishes to approximate the swept volume as precisely as possible. In this work, we will show, that the one-sided Hausdorff distance is the adequate measure for the error of the approximation, when the intended usage is clearance checks, continuous collision detection and maintainability analysis in CAD. We present two implementations that apply the concept and generate a manifold triangle mesh that approximates the outer boundary of a swept volume. Both algorithms are two-phased: a sweeping phase which generates a conservative voxelization of the swept volume, and the actual mesh generation which is based on restricted Delaunay refinement. This approach ensures a high precision of the approximation while respecting conservativeness.rnThe benchmarks for our test are amongst others real world scenarios that come from the automotive industry.rnFurther, we introduce a method to relate parts of an already computed swept volume boundary to those triangles of the generator, that come closest during the sweep. We use this to verify as well as to colorize meshes resulting from our implementations.

Packing a trunk : a physically based approach with full motional freedom

Geometric packing problems may be formulated mathematically as constrained optimization problems. But finding a good solution is a challenging task. The more complicated the geometry of the container or the objects to be packed, the more complex the non-penetration constraints become. In this work we propose the use of a physics engine that simulates a system of colliding rigid bodies. It is a tool to resolve interpenetration conflicts and to optimize configurations locally. We develop an efficient and easy-to-implement physics engine that is specialized for collision detection and contact handling. In succession of the development of this engine a number of novel algorithms for distance calculation and intersection volume were designed and imple- mented, which are presented in this work. They are highly specialized to pro- vide fast responses for cuboids and triangles as input geometry whereas the concepts they are based on can easily be extended to other convex shapes. Especially noteworthy in this context is our ε-distance algorithm - a novel application that is not only very robust and fast but also compact in its im- plementation. Several state-of-the-art third party implementations are being presented and we show that our implementations beat them in runtime and robustness. The packing algorithm that lies on top of the physics engine is a Monte Carlo based approach implemented for packing cuboids into a container described by a triangle soup. We give an implementation for the SAE J1100 variant of the trunk packing problem. We compare this implementation to several established approaches and we show that it gives better results in faster time than these existing implementations.

Rod-shaped plasmonic sensors

Plasmonic nanoparticles exhibit strong light scattering efficiency due to the oscillations of their conductive electrons (plasmon), which are excited by light. For rod-shaped nanoparticles, the resonance position is highly tunable by the aspect ratio (length/width) and the sensitivity to changes in the refractive index in the local environment depends on their diameter, hence, their volume. Therefore, rod-shaped nanoparticles are highly suitable as plasmonic sensors.rnWithin this thesis, I study the formation of gold nanorods and nanorods from a gold-copper alloy using a combination of small-angle X-ray scattering and optical extinction spectroscopy. The latter represents one of the first metal alloy nanoparticle synthesis protocols for producing rod-shaped single crystalline gold-copper (AuxCu(1-x)) alloyed nanoparticles. I find that both length and width independently follow an exponential growth behavior with different time-constants, which intrinsically leads to a switch between positive and negative aspect ratio growth during the course of the synthesis. In a parameter study, I find linear relations for the rate constants as a function of [HAuCl4]/[CTAB] ratio and [HAuCl4]/[seed] ratio. Furthermore, I find a correlation of final aspect ratio and ratio of rate constants for length and width growth rate for different [AgNO3]/[HAuCl4] ratios. I identify ascorbic acid as the yield limiting species in the reaction by the use of spectroscopic monitoring and TEM. Finally, I present the use of plasmonic nanorods that absorb light at 1064nm as contrast agents for photoacoustic imaging (BMBF project Polysound). rnIn the physics part, I present my automated dark-field microscope that is capable of collecting spectra in the range of 450nm to 1750 nm. I show the characteristics of that setup for the spectra acquisition in the UV-VIS range and how I use this information to simulate measurements. I show the major noise sources of the measurements and ways to reduce the noise and how the combination of setup charactersitics and simulations of sensitivity and sensing volume can be used to select appropriate gold rods for single unlabeled protein detection. Using my setup, I show how to estimate the size of gold nano-rods directly from the plasmon linewidth measured from optical single particle spectra. Then, I use this information to reduce the distribution (between particles) of the measured plasmonic sensitivity S by 30% by correcting for the systematic error introduced from the variation in particle size. I investigate the single particle scattering of bowtie structures — structures consisting of two (mostly) equilateral triangles pointing one tip at each other. I simulate the spectra of the structures considering the oblique illumination angle in my setup, which leads to additional plasmon modes in the spectra. The simulations agree well with the measurements form a qualitative point of view.rn

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.

Dressurexperimente zum Kontrast- und Farbensehen von Phoca vitulina und Arctocephalus pusillus

Robben sind amphibische marine Säugetiere. Das bedeutet, dass sie zweirnunterschiedliche Lebensräume, Wasser und Land, bewohnen. Ihre sensorischen Systeme müssen auf beide Medien abgestimmt sein. Gerade für das Sehvermögen ist es eine große Herausforderung, sich den zwei optisch unterschiedlichen Medien anzupassen. Deshalb sind Forscher an dem Sehen von marinen Säugern seit dem zwanzigsten Jahrhundert so sehr interessiert. rnBis heute wird kontrovers diskutiert, ob marine Säugetiere Farbe sehen können, da sie durch einen Gendefekt nur einen Zapfentyp besitzen und somit zu den Zapfen-Monochromaten gehören. Dressurexperimente zeigten jedoch, dass Seebären und Seelöwen in der Lage sind grüne und blaue Testfelder von Graustufen zu unterscheiden (Busch & Dücker, 1987; Griebel & Schmid, 1992).rnUm auszuschließen, dass die Tiere ein Farbensehen über die Unterscheidung von Helligkeit vortäuschen, wurde in der vorliegenden Arbeit zunächst die Kontrasterkennung untersucht und danach Tests auf Farbensehen durchgeführt. Als Versuchstiere dienten zwei Seehunde (Phoca vitulina) und zwei Südafrikanische Seebären (Arctocephalus pusillus). Alle Versuche wurden unter freien Himmel im Zoo Frankfurt durchgeführt. Den Tieren wurden immer drei Testfelder zur Auswahl geboten: zwei waren gleich und zeigten ein homogenen Hintergrund, das dritte zeigte ein Dreieck auf demselben Hintergrund. Die Tiere wurden auf das Dreieck dressiert. In den Versuchen zum Helligkeitskontrast wurden graue Dreiecke auf grauem Hintergrund verwendet. Das Dreieck wurde nicht erkannt bei einem Luminanz-Kontrast (K= LD/(LD+LH)) zwischen 0,03 und -0,12.rnBeim Test auf Farbensehen wurden die Farben Blau, Grün, Gelb und Orange auf grauem Hintergrund verwendet. Die Testreihen zeigten, dass jedes Tier auch in Bereichen von geringem Helligkeitskontrast hohe Wahlhäufigkeiten auf das farbige Dreieck erzielte und somit eindeutig die Farben Blau, Grün und Gelb sehen konnte. Lediglich bei der Farbe Orange kann keine Aussage zum Farbensehen getroffen werden, da das farbige Dreieck immer dunkler war als der Hintergrund. rnZusammenfassend konnte in dieser Arbeit gezeigt werden, dass Seehunde und Seebären in der Lage sind Farbe zu sehen. Vermutlich beruht diese Fähigkeit auf der Interaktion von Stäbchen und Zapfen. rn

Monte Carlo Dose Calculation on Deforming Anatomy

This article presents the implementation and validation of a dose calculation approach for deforming anatomical objects. Deformation is represented by deformation vector fields leading to deformed voxel grids representing the different deformation scenarios. Particle transport in the resulting deformed voxels is handled through the approximation of voxel surfaces by triangles in the geometry implementation of the Swiss Monte Carlo Plan framework. The focus lies on the validation methodology which uses computational phantoms representing the same physical object through regular and irregular voxel grids. These phantoms are chosen such that the new implementation for a deformed voxel grid can be compared directly with an established dose calculation algorithm for regular grids. Furthermore, separate validation of the aspects voxel geometry and the density changes resulting from deformation is achieved through suitable design of the validation phantom. We show that equivalent results are obtained with the proposed method and that no statistically significant errors are introduced through the implementation for irregular voxel geometries. This enables the use of the presented and validated implementation for further investigations of dose calculation on deforming anatomy.

Effect of mesh distortion on the accuracy of high order vorticity-velocity CFD approaches

The numerical solution of the incompressible Navier-Stokes equations offers an alternative to experimental analysis of fluid-structure interaction (FSI). We would save a lot of time and effort and help cut back on costs, if we are able to accurately model systems by these numerical solutions. These advantages are even more obvious when considering huge structures like bridges, high rise buildings or even wind turbine blades with diameters as large as 200 meters. The modeling of such processes, however, involves complex multiphysics problems along with complex geometries. This thesis focuses on a novel vorticity-velocity formulation called the Kinematic Laplacian Equation (KLE) to solve the incompressible Navier-stokes equations for such FSI problems. This scheme allows for the implementation of robust adaptive ordinary differential equations (ODE) time integration schemes, allowing us to tackle each problem as a separate module. The current algortihm for the KLE uses an unstructured quadrilateral mesh, formed by dividing each triangle of an unstructured triangular mesh into three quadrilaterals for spatial discretization. This research deals with determining a suitable measure of mesh quality based on the physics of the problems being tackled. This is followed by exploring methods to improve the quality of quadrilateral elements obtained from the triangles and thereby improving the overall mesh quality. A series of numerical experiments were designed and conducted for this purpose and the results obtained were tested on different geometries with varying degrees of mesh density.