Natural Neighbor Interpolation - Critical Assessment and New Contributions

Interpolation mit Natürlichen Nachbarn - Kritische Betrachtungen und Neue Erkenntnisse

  • In engineering and science, a multitude of problems exhibit an inherently geometric nature. The computational assessment of such problems 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 canonical 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 natural neighbors, the Delaunay triangulation provides robust and efficient 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 affinity 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, a previously proposed method for \(C^2\) 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 different 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 coordinates of the point cloud. Attention is then turned to integrating the flexibility and meritable properties of natural neighbor interpolation into a framework that allows the algorithmically transparent and smooth extrapolation of any known natural neighbor interpolant. Finally, essential properties are proved for a recently introduced novel finite element tessellation technique in which a Delaunay triangulation is transformed into a unique polygonal tessellation.
  • In den Ingenieur- und Naturwissenschaften treten zahlreiche Probleme auf, die eine inhärent geometrische Struktur aufweisen. Um diese rechnergestützt behandeln zu können, werden entsprechende Datenstrukturen und Zugriffsalgorithmen für die digitale Modellierung benötigt. Eine der am weitesten verbreiteten räumlichen Datenstrukturen ist die Delaunaytriangulierung, welche im kanonischen Sinne dual zum Voronoidiagramm ist. Während das Voronoidiagramm eine elegante Möglichkeit bietet, räumliche Abhängigkei-ten zu modellieren, welches sich im Kernkonzept der ``natürlichen Nachbarn'' zusammenfassen lässt, erlaubt die Delaunaytriangulierung den robusten und effizienten Zugriff darauf. Diese nützliche Kombination führt dazu, daß Methoden basierend auf diesen Datenstrukturen in allen Bereichen der Ingenieur- und Naturwissenschaften große Bedeutung haben. Diese Arbeit beschäftigt sich mit Teilproblemen aus einer Vielzahl von Anwendungen, deren Gemeinsamkeit ihre Verbindung zu Voronoidiagrammen und natürlichen Nachbarn ist. Zuerst wird eine Idee untersucht, welche die Verallgemeinerung von B-Splineflächen auf allgemeine, nichtreguläre Knotenstrukturen verspricht. Danach werden explizite Schrit-te vorgestellt, welche die Implementierung eines kürzlich eingeführten neuen Verfahrens zur \(C^2\)-stetigen interpolation über natürlichen Nachbarn erlauben. Die glatte Interpolation mit natürlichen Nachbarn setzt das Vorhandensein von Ableitungsinformationen an den Datenpunkten voraus. Zwei neue Verfahren zur Ableitungsschätzung in unstrukturierten Daten werden vorgestellt, welche auf dem Konzept der natürlichen Nachbarn basieren. In einem verwandten Kontext beschäftigt sich die Arbeit mit der Berechnung diskret harmonischer Funktionen in Punktwolken. Eine wichtige Beobachtung, die hierbei gemacht wurde, zeigt den Zusammenhang zwischen der Approximation des Laplace-Operators mittels lokaler Koordinaten basierend auf natürlichen Nachbarn und der kontinuierlichen Abhängigkeit diskret harmonischer Funktionen von den Koordinaten der Punktwolke. Im Kontext der Datenextrapolation wird eine allgemeine Konstruktion vorgestellt, die mit Hilfe des Konzeptes der natürlichen Nachbarn eine algorithmisch transparente und glatte Erweiterung von Interpolanten über die konvexe Hülle des Datensatzes hinaus ermöglicht. Letztendlich werden in einer ausführlichen Behandlung der Eigenschaften einer vor kurzem einge-führten Netzgenerierungsmethode aus dem Bereich der Finiten Elemente Beweise für eine Reihe vorher angenommener Eigenschaften geliefert.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Tom Axel Bobach
URN:urn:nbn:de:hbz:386-kluedo-23517
Advisor:Georg Umlauf
Document Type:Doctoral Thesis
Language of publication:English
Year of Completion:2009
Year of first Publication:2009
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2008/06/20
Date of the Publication (Server):2009/06/15
Tag:Ableitungsschätzung; Natürliche Nachbarn
Derivative Estimation; Natural Neighbor; Natural Neighbor Interpolation
GND Keyword:Scattered-Data-Interpolation; Interpolation; Voronoi-Diagramm; Delaunay-Triangulierung; Extrapolation; Tesselation
Faculties / Organisational entities:Kaiserslautern - Fachbereich Informatik
DDC-Cassification:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011