Natural neighbor interpolation [Elektronische Ressource] : critical assessment and new contributions / von Tom Bobach

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_kaiserslautern
• Publié le: 01 janvier 2008
• Nombre de lectures: 22
• Langue: Deutsch
• Poids de l'ouvrage: 28 Mo

Extrait

Natural Neighbor Interpolation
-
Critical Assessment and New Contributions
Straight out of My Ass
Dem Fachbereich Informatik
der Technischen Universitat Kaiserslautern
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
(Dr. rer. nat.)
vorgelegte
Dissertation
von
Tom Bobach
Kaiserslautern, im April 2008Zusammenfassung
In den Ingenieur- und Naturwissenschaften treten zahlreiche Probleme auf, die eine
inharent geometrische Struktur aufweisen. Um diese rechnergestutzt behandeln zu konnen,
werden entsprechende Datenstrukturen und Zugri salgorithmen f ur die digitale Model-
lierung benotigt. Eine der am weitesten verbreiteten raumlichen Datenstrukturen ist die
Delaunaytriangulierung, welche im kanonischen Sinne dual zum Voronoidiagramm ist.
Wahrend das Voronoidiagramm eine elegante Moglichkeit bietet, raumlic he Abhangigk ei-
ten zu modellieren, welches sich im Kernkonzept der \naturlichen Nachbarn" zusam-
menfassen lasst, erlaubt die Delaunaytriangulierung den robusten und e zienten Zugri
darauf. Diese nutzliche Kombination fuhrt dazu, da Methoden basierend auf diesen Da-
tenstrukturen in allen Bereichen der Ingenieur- und Naturwissenschaften gro e Bedeutung
haben.
Diese Arbeit beschaftigt sich mit Teilproblemen aus einer Vielzahl von Anwendungen,
deren Gemeinsamkeit ihre Verbindung zu Voronoidiagrammen und naturlichen Nachbarn
ist. Zuerst wird eine Idee untersucht, welche die Verallgemeinerung von B-Spline achen
auf allgemeine, nichtregulare Knotenstrukturen verspricht. Danach werden explizite Schrit-
te vorgestellt, welche die Implementierung eines kurzlich eingefuhrten neuen Verfahrens
2zur C -stetigen interpolation ub er naturlic hen Nachbarn erlauben. Die glatte Interpola-
tion mit naturlichen Nachbarn setzt das Vorhandensein von Ableitungsinformationen an
den Datenpunkten voraus. Zwei neue Verfahren zur Ableitungsschatzung in unstrukturier-
ten Daten werden vorgestellt, welche auf dem Konzept der naturlichen Nachbarn basieren.
In einem verwandten Kontext beschaftigt sich die Arbeit mit der Berechnung diskret har-
monischer Funktionen in Punktwolken. Eine wichtige Beobachtung, die hierbei gemacht
wurde, zeigt den Zusammenhang zwischen der Approximation des Laplace-Operators
mittels lokaler Koordinaten basierend auf naturlichen Nachbarn und der kontinuierlichen
Abhangigkeit diskret harmonischer Funktionen von den Koordinaten der Punktwolke.
Im Kontext der Datenextrapolation wird eine allgemeine Konstruktion vorgestellt, die
mit Hilfe des Konzeptes der naturlichen Nachbarn eine algorithmisch transparente und
glatte Erweiterung von Interpolanten ub er die konvexe Hulle des Datensatzes hinaus
ermoglicht. Letztendlich werden in einer ausfuhrlichen Behandlung der Eigenschaften
einer vor kurzem einge-fuhrten Netzgenerierungsmethode aus dem Bereich der Finiten
Elemente Beweise fur eine Reihe vorher angenommener Eigenschaften geliefert.Abstract
In engineering and science, a multitude of problems exhibit an inherently geometric na-
ture. The computational assessment of such requires an adequate representation
by means of data structures and processing algorithms. One of the most widely adopted
and recognized spatial data structures is the Delaunay triangulation which has its canon-
ical dual in the Voronoi diagram. While the Voronoi diagram provides a simple and
elegant framework to model spatial proximity, the core of which is the concept of natu-
ral neighbors, the Delaunay triangulation provides robust and e cient access to it. This
combination explains the immense popularity of Voronoi- and Delaunay-based methods
in all areas of science and engineering.
This thesis addresses aspects from a variety of applications that share their a nity to the
Voronoi diagram and the natural neighbor concept. First, an idea for the generalization of
B-spline surfaces to unstructured knot sets over Voronoi diagrams is investigated. Then,
2a previously proposed method for C smooth natural neighbor interpolation is backed
with concrete guidelines for its implementation. Smooth natural neighbor interpolation is
also one of many applications requiring derivatives of the input data. The generation of
derivative information in scattered data with the help of natural neighbors is described
in detail. In a di erent setting, the computation of a discrete harmonic function in a
point cloud is considered, and an observation is presented that relates natural neighbor
coordinates to a continuous dependency between discrete harmonic functions and the
co of the point cloud. Attention is then turned to integrating the exibility and
meritable properties of natural neighbor interpolation into a framework that allows the
algorithmically transparent and smooth extrap of any known natural neighbor
interpolant. Finally, essential properties are proved for a recently introduced novel nite
element tessellation technique in which a Delaunay triangulation is transformed into a
unique polygonal tessellation.Acknowledgements
This thesis emerged under formidable supervision by Prof. Georg Umlauf and Prof. Ger-
ald Farin, with further valuable guidance from Prof. Dianne Hansford. Their constant
dependability, both professionally and personally, deserves my deepest gratitude and re-
spect.
I also need to speci cally thank Prof. Hans Hagen, whose dedication in creating new
and interesting interdisciplinary research opportunities enabled a very intense experience
during my time in the international research and training group. The open-minded and
welcoming atmosphere of the whole Kaiserslautern work group enables productive and
pleasant work.
Further thanks go to my collaborators Prof. Martin Hering-Bertram, Alexandru Constan-
tiniu, and Prof. Paul Steinmann, with whom I am happy to have shared such interesting
and challenging research interests.
The invaluable o er of friendship and experienced advice from Prof. Xavier Tricoche and
Dr. Christoph Garth was a big help in all phases of this thesis. Their fruitful discussions
and feedback constantly enriched my work.
In my research I also bene ted from the cooperative and helpful correspondence with a
number of people, whom I would like to thank here. Prof. Hisamoto Hiyoshi was so keen
to provide me with preprints of unpublished research results of his. From Prof. Peter
Alfeld I received a very insightful technical report that greatly supported my work on
extrapolation. While investigating possibilities to generalize natural neighbor coordinates,
Dr. Julia Fl ototto kindly gave me source code on higher order Voronoi diagrams. The
discussion with Prof. Oleg Davidov about scattered data interpolation provided many
insights, and discussion with Prof. N. Sukumar o ered interesting information about
practical applications of natural neighbor interpolation in nite elements.
When having needed to re ect on current issues, I greatly enjoyed the company and ex-
change with Dr. Ariane Middel, who always succeeds in brightening the most worrisome
situation (thank you, Ariane), Dr. Burkhard Lehner, Dr. Kerstin Muller, Dr. Christoph
Funfzig, and many more I fail to mention. I thank all my colleagues in the computer
graphics and geometry group in Kaiserslautern and in the PRISM lab in Phoenix, espe-
cially Mady, Inga, Pushpak, Mahesh, and Roger.
Last but not least, the support of my family and friends was essential to every part of my
work. They deserve my thanks especially for putting up with me during all those times
when work life got the better of me. I love my wife Sophia. Your incredible patience, your
love, and your faith in me kept me going. I deeply thank my parents, who supported me
all the years and paved the way to where and what I am now.Contents
1 Introduction 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Foundations 5
2.1 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 A ne Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Generalized Barycentric Coordinates . . . . . . . . . . . . . . . . . 7
2.1.3 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . . 7
2.1.4 Linear Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Vector Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Multi-Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.3 Multivariate Taylor Series . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Spatial Tessellations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Planar Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Polyhedral Complexes . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.3 Tessellations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.4 The Delaunay Triangulation . . . . . . . . . . . . . . . . . . . . . . 13
2.3.5 The Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.6 The Power . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Bezier and B-Spline Functions . . . . . . . . . . .