Novel insights into the genomic basis of citrus canker based on the genome sequences of two strains of Xanthomonas fuscans subsp. aurantifolii

Abstract Background Citrus canker is a disease that has severe economic impact on the citrus industry worldwide. There are three types of canker, called A, B, and C. The three types have different phenotypes and affect different citrus species. The causative agent for type A is Xanthomonas citri subsp. citri, whose genome sequence was made available in 2002. Xanthomonas fuscans subsp. aurantifolii strain B causes canker B and Xanthomonas fuscans subsp. aurantifolii strain C causes canker C. Results We have sequenced the genomes of strains B and C to draft status. We have compared their genomic content to X. citri subsp. citri and to other Xanthomonas genomes, with special emphasis on type III secreted effector repertoires. In addition to pthA, already known to be present in all three citrus canker strains, two additional effector genes, xopE3 and xopAI, are also present in all three strains and are both located on the same putative genomic island. These two effector genes, along with one other effector-like gene in the same region, are thus good candidates for being pathogenicity factors on citrus. Numerous gene content differences also exist between the three cankers strains, which can be correlated with their different virulence and host range. Particular attention was placed on the analysis of genes involved in biofilm formation and quorum sensing, type IV secretion, flagellum synthesis and motility, lipopolysacharide synthesis, and on the gene xacPNP, which codes for a natriuretic protein. Conclusion We have uncovered numerous commonalities and differences in gene content between the genomes of the pathogenic agents causing citrus canker A, B, and C and other Xanthomonas genomes. Molecular genetics can now be employed to determine the role of these genes in plant-microbe interactions. The gained knowledge will be instrumental for improving citrus canker control.

Distribution of nitrogen fixation and nitrogenase-like sequences amongst microbial genomes

Abstract Background The metabolic capacity for nitrogen fixation is known to be present in several prokaryotic species scattered across taxonomic groups. Experimental detection of nitrogen fixation in microbes requires species-specific conditions, making it difficult to obtain a comprehensive census of this trait. The recent and rapid increase in the availability of microbial genome sequences affords novel opportunities to re-examine the occurrence and distribution of nitrogen fixation genes. The current practice for computational prediction of nitrogen fixation is to use the presence of the nifH and/or nifD genes. Results Based on a careful comparison of the repertoire of nitrogen fixation genes in known diazotroph species we propose a new criterion for computational prediction of nitrogen fixation: the presence of a minimum set of six genes coding for structural and biosynthetic components, namely NifHDK and NifENB. Using this criterion, we conducted a comprehensive search in fully sequenced genomes and identified 149 diazotrophic species, including 82 known diazotrophs and 67 species not known to fix nitrogen. The taxonomic distribution of nitrogen fixation in Archaea was limited to the Euryarchaeota phylum; within the Bacteria domain we predict that nitrogen fixation occurs in 13 different phyla. Of these, seven phyla had not hitherto been known to contain species capable of nitrogen fixation. Our analyses also identified protein sequences that are similar to nitrogenase in organisms that do not meet the minimum-gene-set criteria. The existence of nitrogenase-like proteins lacking conserved co-factor ligands in both diazotrophs and non-diazotrophs suggests their potential for performing other, as yet unidentified, metabolic functions. Conclusions Our predictions expand the known phylogenetic diversity of nitrogen fixation, and suggest that this trait may be much more common in nature than it is currently thought. The diverse phylogenetic distribution of nitrogenase-like proteins indicates potential new roles for anciently duplicated and divergent members of this group of enzymes.

A Skyrme-like model with an exact BPS bound

We propose a new Skyrme-like model with fields taking values on the sphere S3 or, equivalently, on the group SU(2). The action of the model contains a quadratic kinetic term plus a quartic term which is the same as that of the Skyrme-Faddeev model. The novelty of the model is that it possess a first order Bogomolny type equation whose solutions automatically satisfy the second order Euler-Lagrange equations. It also possesses a lower bound on the static energy which is saturated by the Bogomolny solutions. Such Bogomolny equation is equivalent to the so-called force free equation used in plasma and solar Physics, and which possesses large classes of solutions. An old result due to Chandrasekhar prevents the existence of finite energy solutions for the force free equation on the entire three- dimensional space R3. We construct new exact finite energy solutions to the Bogomolny equations for the case where the space is the three-sphere S3, using toroidal like coordinates.

Variational second order flow estimation for PIV sequences

[EN] We present in this paper a variational approach to accurately estimate simultaneously the velocity field and its derivatives directly from PIV image sequences. Our method differs from other techniques that have been presented in the literature in the fact that the energy minimization used to estimate the particles motion depends on a second order Taylor development of the flow. In this way, we are not only able to compute the motion vector field, but we also obtain an accurate estimation of their derivatives. Hence, we avoid the use of numerical schemes to compute the derivatives from the estimated flow that usually yield to numerical amplification of the inherent uncertainty on the estimated flow. The performance of our approach is illustrated with the estimation of the motion vector field and the vorticity on both synthetic and real PIV datasets.

An evolutive approach for smile recognition in video sequences

Facial expression recognition is one of the most challenging research areas in the image recognition ¯eld and has been actively studied since the 70's. For instance, smile recognition has been studied due to the fact that it is considered an important facial expression in human communication, it is therefore likely useful for human–machine interaction. Moreover, if a smile can be detected and also its intensity estimated, it will raise the possibility of new applications in the future

Aldo Rossi, autobiografia scientifica: scrittura come progetto. Indagine critica tra scrittura e progetto di architettura

«In altri termini mi sfuggiva e ancora oggi mi sfugge gran parte del significato dell’evoluzione del tempo; come se il tempo fosse una materia che osservo dall’esterno. Questa mancanza di evoluzione è fonte di alcune mie sventure ma anche mi appartiene con gioia.» Aldo Rossi, Autobiografia scientifica. The temporal dimension underpinning the draft of Autobiografia scientifica by Aldo Rossi may be referred to what Lucien Lévy-Bruhl, the well-known French anthropologist, defines as “primitive mentality” and “prelogical” conscience : the book of life has lost its page numbers, even punctuation. For Lévy-Bruhl, but certainly for Rossi, life or its summing up becomes a continuous account of ellipses, gaps, repetitions that may be read from left to right or viceversa, from head to foot or viceversa without distinction. Rossi’s autobiographical writing seems to accept and support the confusion with which memories have been collected, recording them after the order memory gives them in the mental distillation or simply according to the chronological order in which they have happened. For Rossi, the confusion reflects the melting of memory elements into a composite image which is the result of a fusion. He is aware that the same sap pervades all memories he is going to put in order: each of them has got a common denominator. Differences have diminished, almost faded; the quick glance is prevalent over the distinction of each episode. Rossi’s writing is beyond the categories dependent on time: past and present, before and now. For Rossi, the only repetition – the repetition the text will make possible for an indefinite number of times – gives peculiarity to the event. As Gilles Deleuze knows, “things” may only last as “singleness”: more frequent the repetition is, more singular is the memory phenomenon that recurs, because only what is singular magnifies itself and happens endlessly forever. Rossi understands that “to raise the first time to nth forever”, repetition becomes glorification . It may be an autobiography that, celebrating the originality, enhances the memory event in the repetition; in fact it greatly differs from the biographical reproduction, in which each repetition is but a weaker echo, a duller copy, provided with a smaller an smaller power in comparison with the original. Paradoxically, for Deleuze the repetition asserts the originality and singularity of what is repeated. Rossi seems to share the thought expressed by Kierkegaard in the essay Repetition: «The hope is a graceful maiden slipping through your fingers; the memory of an elderly woman, indeed pretty, but never satisfactory if necessary; the repetition is a loved friend you are never tired of, as it is only the new to make you bored. The old never bores you and its presence makes you happy [...] life is but a repetition [...] here is the beauty of life» . Rossi knows well that repetition hints at the lasting stability of cosmic time. Kierkegaard goes on: «The world exists, and it exists as a repetition» . Rossi devotes himself, on purpose and in all conscience, to collect, to inventory and «to review life», his own life, according to a recovery not from the past but of the past: a search work, the «recherche du temps perdu», as Proust entitled his masterpiece on memory. If you want the past time to be not wasted, you must give it presence. «Memoria e specifico come caratteristiche per riconoscere se stesso e ciò che è estraneo mi sembravano le più chiare condizioni e spiegazioni della realtà. Non esiste uno specifico senza memoria, e una memoria che non provenga da un momento specifico; e solo questa unione permette la conoscenza della propria individualità e del contrario (self e non-self)» . Rossi wants to understand himself, his own character; it is really his own character that requires to be understood, to increase its own introspective ability and intelligence. «Può sembrare strano che Planck e Dante associno la loro ricerca scientifica e autobiografica con la morte; una morte che è in qualche modo continuazione di energia. In realtà, in ogni artista o tecnico, il principio della continuazione dell’energia si mescola con la ricerca della felicità e della morte» . The eschatological incipit of Rossi’s autobiography refers to Freud’s thought in the exact circularity of Dante’s framework and in as much exact circularity of the statement of the principle of the conservation of energy: in fact it was Freud to connect repetition to death. For Freud, the desire of repetition is an instinct rooted in biology. The primary aim of such an instinct would be to restore a previous condition, so that the repeated history represents a part of the past (even if concealed) and, relieving the removal, reduces anguish and tension. So, Freud ask himself, what is the most remote state to which the instinct, through the repetition, wants to go back? It is a pre-vital condition, inorganic of the pure entropy, a not-to-be condition in which doesn’t exist any tension; in other words, Death. Rossi, with the theme of death, introduces the theme of circularity which further on refers to the sense of continuity in transformation or, in the opposite way, the transformation in continuity. «[...] la descrizione e il rilievo delle forme antiche permettevano una continuità altrimenti irripetibile, permettevano anche una trasformazione, una volta che la vita fosse fermata in forme precise» . Rossi’s attitude seems to hint at the reflection on time and – in a broad sense – at the thought on life and things expressed by T.S. Eliot in Four Quartets: «Time present and time past / Are both perhaps present in time future, / And time future is contained in time past. / I all time is eternally present / All time is unredeemable. / What might have been is an abstraction / Remaining perpetual possibility / Only in a word of speculation. / What might have been and what has been / Point to one end, which is always present. [...]» . Aldo Rossi’s autobiographical story coincides with the description of “things” and the description of himself through the things in the exact parallel with craft or art. He seems to get all things made by man to coincide with the personal or artistic story, with the consequent immediate necessity of formulating a new interpretation: the flow of things has never met a total stop; all that exists nowadays is but a repetition or a variant of something existing some time ago and so on, without any interruption until the early dawnings of human life. Nevertheless, Rossi must operate specific subdivisions inside the continuous connection in time – of his time – even if limited by a present beginning and end of his own existence. This artist, as an “historian” of himself and his own life – as an auto-biographer – enjoys the privilege to be able to decide if and how to operate the cutting in a certain point rather than in another one, without being compelled to justify his choice. In this sense, his story is a matter very ductile and flexible: a good story-teller can choose any moment to start a certain sequence of events. Yet, Rossi is aware that, beyond the mere narration, there is the problem to identify in history - his own personal story – those flakings where a clean cut enables the separation of events of different nature. In order to do it, he has to make not only an inventory of his own “things”, but also to appeal to authority of the Divina Commedia started by Dante when he was 30. «A trent’anni si deve compiere o iniziare qualcosa di definitivo e fare i conti con la propria formazione» . For Rossi, the poet performs his authority not only in the text, but also in his will of setting out on a mystical journey and handing it down through an exact descriptive will. Rossi turns not only to the authority of poetry, but also evokes the authority of science with Max Plank and his Scientific Autobiography, published, in Italian translation, by Einaudi, 1956. Concerning Planck, Rossi resumes an element seemingly secondary in hit account where the German physicist «[...] risale alle scoperte della fisica moderna ritrovando l’impressione che gli fece l’enunciazione del principio di conservazione dell’energia; [...]» . It is again the act of describing that links Rossi to Planck, it is the description of a circularity, the one of conservation of energy, which endorses Rossi’s autobiographical speech looking for both happiness and death. Rossi seems to agree perfectly to the thought of Planck at the opening of his own autobiography: «The decision to devote myself to science was a direct consequence of a discovery which was never ceased to arouse my enthusiasm since my early youth: the laws of human thought coincide with the ones governing the sequences of the impressions we receive from the world surrounding us, so that the mere logic can enable us to penetrate into the latter one’s mechanism. It is essential that the outer world is something independent of man, something absolute. The search of the laws dealing with this absolute seems to me the highest scientific aim in life» . For Rossi the survey of his own life represents a way to change the events into experiences, to concentrate the emotion and group them in meaningful plots: «It seems, as one becomes older. / That the past has another pattern, and ceases to be a mere sequence [...]» Eliot wrote in Four Quartet, which are a meditation on time, old age and memory . And he goes on: «We had the experience but missed the meaning, / And approach to the meaning restores the experience / In a different form, beyond any meaning [...]» . Rossi restores in his autobiography – but not only in it – the most ancient sense of memory, aware that for at least 15 centuries the Latin word memoria was used to show the activity of bringing back images to mind: the psychology of memory, which starts with Aristotele (De Anima), used to consider such a faculty totally essential to mind. Keith Basso writes: «The thought materializes in the form of “images”» . Rossi knows well – as Aristotele said – that if you do not have a collection of mental images to remember – imagination – there is no thought at all. According to this psychological tradition, what today we conventionally call “memory” is but a way of imagining created by time. Rossi, entering consciously this stream of thought, passing through the Renaissance ars memoriae to reach us gives a great importance to the word and assumes it as a real place, much more than a recollection, even more than a production and an emotional elaboration of images.

Analysis of eruptive and seismic sequences to improve the short-and long-term eruption forecasting

Forecasting the time, location, nature, and scale of volcanic eruptions is one of the most urgent aspects of modern applied volcanology. The reliability of probabilistic forecasting procedures is strongly related to the reliability of the input information provided, implying objective criteria for interpreting the historical and monitoring data. For this reason both, detailed analysis of past data and more basic research into the processes of volcanism, are fundamental tasks of a continuous information-gain process; in this way the precursor events of eruptions can be better interpreted in terms of their physical meanings with correlated uncertainties. This should lead to better predictions of the nature of eruptive events. In this work we have studied different problems associated with the long- and short-term eruption forecasting assessment. First, we discuss different approaches for the analysis of the eruptive history of a volcano, most of them generally applied for long-term eruption forecasting purposes; furthermore, we present a model based on the characteristics of a Brownian passage-time process to describe recurrent eruptive activity, and apply it for long-term, time-dependent, eruption forecasting (Chapter 1). Conversely, in an effort to define further monitoring parameters as input data for short-term eruption forecasting in probabilistic models (as for example, the Bayesian Event Tree for eruption forecasting -BET_EF-), we analyze some characteristics of typical seismic activity recorded in active volcanoes; in particular, we use some methodologies that may be applied to analyze long-period (LP) events (Chapter 2) and volcano-tectonic (VT) seismic swarms (Chapter 3); our analysis in general are oriented toward the tracking of phenomena that can provide information about magmatic processes. Finally, we discuss some possible ways to integrate the results presented in Chapters 1 (for long-term EF), 2 and 3 (for short-term EF) in the BET_EF model (Chapter 4).

Molekulare Untersuchung des Wolf-Hirschhorn-Syndroms

Das Wolf-Hirschhorn-Syndrom (WHS) ist ein komplexes und variables Fehlbildungs- Retardierungssyndrom, das durch Deletion in der distalen Chromosomenregion 4p16.3 hervorgerufen wird und dessen Ätiologie und Pathogenese bisher weitgehend unverstanden sind. Die Zielsetzung in der vorliegenden Arbeit bestand in der Identifizierung und vorläufigen Charakterisierung neuer Gene, die an der Entstehung des Syndroms beteiligt sein könnten. Die Wolf-Hirschhorn-Syndrom-kritische Region (WHSCR) konnte zu Beginn der vorliegenden Arbeit auf einen ca. 2 Mb großen Bereich zwischen den Markern D4S43 und D4S142 eingegrenzt werden. Für die Identifizierung neuer Gene wurden zunächst drei größere genomische Cosmid-/PAC-Contigs (I-III) im Bereich der Marker D4S114 bis D4S142 erstellt und mittels Exonamplifikation auf transkribierte Bereiche (Exons) untersucht. Es konnten insgesamt 67 putative 'Exons' isoliert werden, von denen einige bereits bekannten Genen (ZNF141, PDEB, MYL5, GAK, DAGK4 und FGFR3) entsprechen. Zwei dieser Gene konnten im Rahmen dieser Arbeit erstmals (DAGK4) bzw. genauer (GAK) in die distale Region 4p16.3 kartiert werden. Die restlichen Exons können aufgrund von Homologievergleichen und/oder EST-cDNA-Homologien vermutlich neuen Genen oder auch Pseudogenen (z. B. YWEE1hu) zugeordnet werden. Durch die im Verlaufe der vorliegenden Arbeit publizierte weitere Eingrenzung der WHSCR auf einen 165 Kb-großen Bereich proximal des FGFR3-Gens konzentrierten sich weitere Untersuchungen auf die detaillierte Analyse der WHSCR zwischen dem Marker D4S43 und FGFR3. Mit Hilfe von Exonamplifikation bzw. computergestützter Auswertung vorliegender Sequenzdaten aus diesem Bereich ('GRAIL', 'GENSCAN' und Homologievergleiche in den EST-Datenbanken des NCBI) konnten mehrere neue Gene identifiziert werden. In distaler-proximaler Reihenfolge handelt es sich dabei um die Gene LETM1, 51, 43, 45, 57 und POL4P. LETM1 kodiert für ein putatives Transmembran-Protein mit einem Leucin-Zipper- und zwei EF-Hand-Motiven und könnte aufgrund seiner möglichen Beteiligung an der Ca2+-Homeostase und/oder der Signal-transduktion zu Merkmalen des WHS (Krampfanfällen, mentale Retardierung und muskuläre Hypotonie) beitragen. Das Gen 51 entspricht einem in etwa zeitgleich durch Stec et al. (1998) und Chesi et al. (1998) als WHSC1 bzw. MMSET bezeichnetem Gen und wurde daher nicht weiter charakterisiert. Es wird genauso wie das Gen 43, das zeitgleich von Wright et al. (1999b) als WHSC2 beschrieben werden konnte und eine mögliche Rolle bei der Transkriptionselongation spielt, ubiquitär exprimiert. Das in der vorliegenden Arbeit identifizierte Gen 45 zeigt demgegenüber ein ausgesprochen spezifisches Expressionsmuster (in Nervenzellen des Gehirns sowie in Spermatiden). Dies stellt zusammen mit der strukturellen Ähnlichkeit des putativen Genprodukts zu Signalmolekülen einen interessanten Zusammenhang zu Merkmalen des WHS (beispielsweise Kryptorchismus, Uterusfehlbildungen oder auch neurologische Defekte) her. Demgegenüber handelt es sich bei dem Gen 57 möglicherweise um ein trunkiertes Pseudogen des eRFS-Gens auf Chromosom 6q24 (Wallrapp et al., 1998). Das POL4P-Gen schließlich stellt allein aufgrund seiner genomischen Lokalisation sowie seiner möglichen Funktion (als DNA-Polymerase-ähnliches Gen) kein gutes Kandidatengen für spezifische Merkmale des Syndroms dar und wurde daher nicht im Detail charakterisiert. Um die Beteiligung der Gene an der Ätiologie und Pathogenese des Syndroms zu verstehen, ist die Entwicklung eines Mausmodells (über das Einfügen gezielter Deletionen in das Mausgenom) geplant. Um dies zu ermöglichen, wurde in der vorliegenden Arbeit die Charakterisierung der orthologen Region bei der Maus vorgenommen. Zunächst wurden die orthologen Gene der Maus (Letm1, Whsc1, Gen 43 (Whsc2h), Gen 45 und Pol4p) identifiziert. Durch die Erstellung sowie die genaue Kartierung eines murinen genomischen P1/PAC-Klon-Contigs konnte gezeigt werden, daß die murinen Gene Fgfr3, Letm1, Whsc1, Gen 43 (Whsc2h), Gen 45 und Pol4p sowie einige weitere der überprüften EST-cDNA-Klone der Maus in einem durchgehenden Syntänieblock zwischen Mensch (POL4P bis FGFR3) und Maus (Mmu 5.20) enthalten sind, der in seiner genomischen Ausdehnung in etwa den Verhältnissen beim Menschen (zwischen POL4P und FGFR3) entspricht.

Untersuchung magnetischer Nanostrukturen mittels Rastertunnelspektroskopie und Kerr-Magnetometrie am Beispiel von Fe, Co, Co-Fe und Fe-Mn Nanostrukturen

Nach einer kurzen Einführung in die Entwicklung der magnetischen Anwendungen, werden in Kapitel 2 und 3 die physikalischen Grundlagen der Messmethoden, insbesondere die Rastertunnelspektroskopie und Kerr-Magnetometrie, sowie der experimentelle Aufbau erläutert. Kapitel 4 beschäftigt sich mit den magnetischen Eigenschaften von quasi ein-dimensionalen ferromagnetischen Nanostreifen und Monolagen, die durch Selbstorganisation auf einem Wolfram(110)-Einkristall mit vizinaler und glatter Oberfläche präpariert werden. Hierbei wird die Temperaturabhängigkeit der magnetischen Größen, wie Remanenz, Sättigungsmagnetisierung und Suszeptibilität, sowie die Auswirkung einer Abdeckung des Systems auf die Domänenwandenergie und Anisotropie untersucht. Zusätzlich wird die Kopplung von parallelen Nanostreifen in Abhängigkeit des Streifenabstandes betrachtet. In Kapitel 5 werden das Wachstum und die Morphologie von Co-Monolagen auf W(110) untersucht. Der Übergang von pseudomorphem zu dicht gepacktem Wachstum in der Monolage wird mit Hilfe der Rastertunnelspektroskopie sichtbar gemacht, ebenso wie unterschiedliche Stapelfolgen in Tripellagen Co-Systemen. Atomar aufgelöste Rastertunnelmikroskopie erlaubt die genauen Atompositionen der Oberfläche zu bestimmen und mit theoretischen Wachstumsmodellen zu vergleichen. Auf die Untersuchung zwei-dimensionaler binärer Co-Fe und Fe-Mn Legierungen auf W(110) wird in Kapitel 6 eingegangen. Mit einer Präparationstemperatur von T=520 K ist es möglich, atomar geordnete Co-Fe Legierungsmonolagen wachsen zu lassen. Ein direkter Zusammenhang zwischen der Magnetisierung und der lokalen Zustandsdichte in Abhängigkeit der Legierungszusammensetzung wird gezeigt.

Exact Algorithms for Different Classes of Vehicle Routing Problems

We deal with five problems arising in the field of logistics: the Asymmetric TSP (ATSP), the TSP with Time Windows (TSPTW), the VRP with Time Windows (VRPTW), the Multi-Trip VRP (MTVRP), and the Two-Echelon Capacitated VRP (2E-CVRP). The ATSP requires finding a lest-cost Hamiltonian tour in a digraph. We survey models and classical relaxations, and describe the most effective exact algorithms from the literature. A survey and analysis of the polynomial formulations is provided. The considered algorithms and formulations are experimentally compared on benchmark instances. The TSPTW requires finding, in a weighted digraph, a least-cost Hamiltonian tour visiting each vertex within a given time window. We propose a new exact method, based on new tour relaxations and dynamic programming. Computational results on benchmark instances show that the proposed algorithm outperforms the state-of-the-art exact methods. In the VRPTW, a fleet of identical capacitated vehicles located at a depot must be optimally routed to supply customers with known demands and time window constraints. Different column generation bounding procedures and an exact algorithm are developed. The new exact method closed four of the five open Solomon instances. The MTVRP is the problem of optimally routing capacitated vehicles located at a depot to supply customers without exceeding maximum driving time constraints. Two set-partitioning-like formulations of the problem are introduced. Lower bounds are derived and embedded into an exact solution method, that can solve benchmark instances with up to 120 customers. The 2E-CVRP requires designing the optimal routing plan to deliver goods from a depot to customers by using intermediate depots. The objective is to minimize the sum of routing and handling costs. A new mathematical formulation is introduced. Valid lower bounds and an exact method are derived. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.

Exact computation of the adjacency graph of an arrangement of quadrics

Präsentiert wird ein vollständiger, exakter und effizienter Algorithmus zur Berechnung des Nachbarschaftsgraphen eines Arrangements von Quadriken (Algebraische Flächen vom Grad 2). Dies ist ein wichtiger Schritt auf dem Weg zur Berechnung des vollen 3D Arrangements. Dabei greifen wir auf eine bereits existierende Implementierung zur Berechnung der exakten Parametrisierung der Schnittkurve von zwei Quadriken zurück. Somit ist es möglich, die exakten Parameterwerte der Schnittpunkte zu bestimmen, diese entlang der Kurven zu sortieren und den Nachbarschaftsgraphen zu berechnen. Wir bezeichnen unsere Implementierung als vollständig, da sie auch die Behandlung aller Sonderfälle wie singulärer oder tangentialer Schnittpunkte einschließt. Sie ist exakt, da immer das mathematisch korrekte Ergebnis berechnet wird. Und schließlich bezeichnen wir unsere Implementierung als effizient, da sie im Vergleich mit dem einzigen bisher implementierten Ansatz gut abschneidet. Implementiert wurde unser Ansatz im Rahmen des Projektes EXACUS. Das zentrale Ziel von EXACUS ist es, einen Prototypen eines zuverlässigen und leistungsfähigen CAD Geometriekerns zu entwickeln. Obwohl wir das Design unserer Bibliothek als prototypisch bezeichnen, legen wir dennoch größten Wert auf Vollständigkeit, Exaktheit, Effizienz, Dokumentation und Wiederverwendbarkeit. Über den eigentlich Beitrag zu EXACUS hinaus, hatte der hier vorgestellte Ansatz durch seine besonderen Anforderungen auch wesentlichen Einfluss auf grundlegende Teile von EXACUS. Im Besonderen hat diese Arbeit zur generischen Unterstützung der Zahlentypen und der Verwendung modularer Methoden innerhalb von EXACUS beigetragen. Im Rahmen der derzeitigen Integration von EXACUS in CGAL wurden diese Teile bereits erfolgreich in ausgereifte CGAL Pakete weiterentwickelt.