Computation of medial sets in Riemannian manifolds [Elektronische Ressource] / von Henning Naß

Henning Naß

Sujets

• Mathematics

Informations

• Publié par: gottfried_wilhelm_leibniz_universitat_hannover
• Publié le: 01 janvier 2007
• Nombre de lectures: 42
• Langue: Deutsch
• Poids de l'ouvrage: 3 Mo

Extrait

Computation of Medial Sets in
Riemannian Manifolds
Von der Fakult¨at fur¨ Elektrotechnik und Informatik
der Gottfried Wilhelm Leibniz Universit¨at Hannover
zur Erlangung des Grades eines
DOKTORS DER NATURWISSENSCHAFTEN
Dr. rer. nat.
genehmigte Dissertation von
Dipl.-Math. Henning Naß
geboren am 14. September 1975 in Wildeshausen
2007Referent: Prof. Dr. Franz-Erich Wolter
Institut fur¨ Mensch-Maschine-Kommunikation
Gottfried Wilhelm Leibniz Universit¨at Hannover
Koreferent: Dr.-Ing habil. Peter Milbradt
Institut fur¨ Bauinformatik
Gottfried Wilhelm Leibniz Universit¨at Hannover
Tag der Promotion: 13. September 2007Zusammenfassung
Die Riemannsche Geometrie ist ein klassisches Feld der Differentialgeometrie, das eini-
ge wesentliche Ideen fur¨ eine Verallgemeinerung des Cut-Locus-Konzepts beherbergt.
Falls z.B. (M,d) eine Riemannsche Mannigfaltigkeit darstellt mit induzierter Metrik
d, dann lautet eine m¨ogliche Definition des Cut-Locus C einer Referenzmenge AA
folgendermaßen: C besteht aus dem Abschluß der Menge aller Punkte außerhalb A,A
wo die Distanzfunktion d nicht differenzierbar ist. Dieses Konzept des Cut Locus istA
eng verwandt mit den Konzepten medialer Mengen.
Das vorliegende Dokument dient als Beitrag fur¨ berechnende Geometrien von medi-
alen Mengen auf Riemannschen Mannigfaltigkeiten. Diese Arbeit setzt sich insoweit
von bestehenden Arbeiten ab, als dass sie davon ausgeht, dass alle vorkommenden
Objekte parametrisiert sind. Fur¨ die Berechnung von medialen Mengen werden wir
im Wesentlichen mit den medialen Differentialgleichungen operieren, wobei es sich um
ein gew¨ohnliches implizites Differentialgleichungssystem handelt. Ursprung¨ lich wurde
diese Idee schon in fruheren¨ Arbeiten benutzt. Allerdings bezogen sich diese Arbeiten
aufFl¨achenderDimension2. DaherwirdindieserArbeiteingroßerWertaufdieVerall-
gemeinerungderentsprechendenErgebnisseaufh¨oher-dimensionaleMannigfaltigkeiten
gelegt sowie auf verbesserte numerische Verfahren.
Die topologische Vielfalt von medialen Mengen kann hier nicht in vollem Umfang
beruc¨ ksichtigt werden. Vielmehr geht es in dieser Arbeit um die Betrachtung von
Situationen, die in Anwendungen der realen Welt zum Tragen kommen. Einige der
pr¨asentierten Ideen stammen aus bestehenden Arbeiten, die sich mit dem Verhalten
von medialen Mengen in euklidischen R¨aumen besch¨aftigen. Es gibt tats¨achlich sehr
viele Analogien zu diesem Fall.
Die wesentlichen Neuerungen im Vergleich zu bestehenden Arbeiten liegen haupts¨ach-
lich in der Entwicklung von Homotopieverfahren, mit denen es z.B. m¨oglich ist das
Problem der kurzesten¨ Wege hinreichend genau zu l¨osen. Ebenso geh¨ort auch der
geod¨atische mediale Modellierer zu einer dieser Neuerungen, fu¨r dessen Implementa-
tion vor allem auf eine naturlic¨ here Gestaltung von Freiformfl¨achen Wert gelegt wurde.
Die mediale Achse ist ein hervorragender Ansatz fur¨ die Parzellierung von dreidimen-
sionalen Objekten, die dann z.B. fur¨ die Finite Elemente Simulationen benutzt werden
k¨onnen. Diese Arbeit enth¨alt Beispiele fur¨ Berechnungen von medialen Fl¨achen und
von Voronoi-Diagrammen, um die theoretischen Grundlagen zu erh¨arten.
Keywords: Geod¨atische Mediale Achse, Mediale Differentialgleichungen,
Geod¨atisches Voronoi-DiagrammAbstract
Riemannian geometry is a classical field of differentiable geometry that provides some
important ideas being useful for the generalisation of the cut locus concepts. If for
example (M,d) is a Riemannian manifold with the induced intrinsic metricd, then the
definitionofthecutlocusC ofareferencesetAcouldbeas follows: ThecutlocusCA A
is the closure of all points inM\A where the distance functiond is not differentiable.A
Thisdefinitionisequivalenttosomeotherdefinitionsthatwillbeexplainedthroughout
this thesis.
Thepresentdocumentservesasacontributiontothecomputationalgeometryofmedial
sets and the cut locus in Riemannian manifolds. This approach is mainly based on the
fact that every occurring object is given in parametric representation which provides
the reason why this work differs heavily from existing works. For the computation of
medial sets we will employ the so called medial differential equations which is a linear
system of implicit ordinary differential equations. Originally this idea was already
presentedinearlierworksincaseoftwo-dimensionalRiemannianmanifolds. Therefore,
this work mainly focuses on the generalisation of the aforementioned concepts to the
higher dimensional cases and an improved numerical analysis.
The topological variety of medial sets can not be discussed here to the full extent
since this would go beyond the scope of this thesis. This work is rather interested in
situations that are typical in the context of real world applications. Some of the ideas
presented refer to existing works that treat the behaviour of medial sets in Euclidean
spaces and in fact there are many analogies to this case.
The essential innovation of this work in comparison to other works lies mainly in
the development of homotopy methods that make it possible to accurately solve the
shortest join problem on hypersurfaces. In addition, the geodesic modeller was one
of the improvements of this work that differs from other modelling tools by the fact
that the construction of freeform surface has become more natural. The medial axis
of solids is a powerful approach for the construction of tessellations that can be used
for exmple as a coarse grid in Finite Element applications. This thesis includes some
examplesofcomputationsofmedialsurfaces and of Voronoi diagrams toilluminatethe
obtained results.
Keywords: Geodesic Medial Axis, Geodesic Voronoi Diagram, Medial Dif-
ferential EquationsAcknowledgements
The present document is a product of studies over the past three years at the Gottfried
Wilhelm Leibniz Universit¨at Hannover. At the beginning of that time I applied for
a scholarship at the Graduiertenkolleg 615. Prof. Dr. E. Stephan being the speaker
of the Graduiertenkolleg 615 admitted me as a member of the Graduiertenkolleg. I
acknowledge him for the chance of having that membership. I would also like to thank
my adviser Prof. Wolter for inviting me to join the Graduiertenkolleg and for his
willingness to support me and to give me helpful advice in every respect. Prof. Wolter
made arrangements that I obtained an invitation to a research visit at MIT in Summer
06 where I could pursue research of my thesis project leading to substantial results in
a creative and stimulating environment. I acknowledge Tobias Pick who accompanied
me for his open ears and his assistance with regard to the organisational problems that
arose at the beginning of that trip. I acknowledge my co-adviser PD Dr.-Ing. habil.
Peter Milbradt for revising my thesis and his help to accomplish this work.
IwouldliketothankthewholeWelfenlabresearchgroupforthesupportandespecially
Cem Do˘gan and Hannes Thielhelm for accomplishing their master thesis and diploma
thesis under my supervision. This work would not have been possible without them. I
thank Prof. Wolter for revising my thesis.
I acknowledge my family and especially my mother, my brother and my sister-in-law
for supporting me all along. Although they could not support me in technical terms
they kept me grounded in times when my progress with this thesis was slow. I thank
my girlfriend Andrea Hohnhorst for her frankness and her patience she has exercised
during that time. Finally, I would like to acknowledge Henrik L¨ohren for revising the
final version of my PhD thesis.
Henning Naß, Hannover, August 2007Contents
1 Introduction 3
2 Preliminaries 8
2.1 A First Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Central Difference Quotients . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Boundary Value Problems . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Homotopy Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.1 Bifurcation Theory . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Elements Of Differential Geometry 23
3.1 Manifolds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Riemannian Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.1 The Curvature Tensor . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Jacobi Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 The Notion Of Tubes And Fermi Coordinates . . . . . . . . . . . . . . 32
3.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 Offsets And Offset Functions 36
4.1 Difference Between Offsets And Offset Functions . . . . . . . . . . . . . 36
4.2 Offsets On 2-dimensional Manifolds . . . . . . . . . . . . . . . . . . . . 37
4.2.1 Point Offsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2.2 Offsets of Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Offsets On 3-dimensional Manifolds . . . . . . . . . . . . . . . . . . . . 40
4.3.1 Offsets of Points . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3.2 Offsets of Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3.3 O