Geometric applications of principal component analysis

Abstract

Bounding boxes are used in many applications for simplification of point sets or complex shapes. For example, in computer graphics, bounding boxes are used to maintain hierarchical data structures for fast rendering of a scene or for collision detection. Additional applications include those in shape analysis and shape simplification, or in statistics, for storing and performing range- search queries on a large database of samples. A frequently used heuristic for computing a bounding box of a set of points is based on principal component analysis. The principal components of the point set define the axes of the bounding box. Once the axis directions are given, the dimension of the bounding box is easily found by the extreme values of the projection of the points on the corresponding axis. Computing a PCA bounding box of a discrete point set in $\mathbb{R}^d$ depends linearly on the number of points. The popularity of this heuristic, besides its speed, lies in its easy implementation and in the fact that usually PCA bounding boxes are tight- fitting. In this thesis we investigate the quality of the PCA bounding boxes. We give bounds on the worst case ratio of the volume of the PCA bounding box and the volume of the minimum volume bounding box. We present examples of point sets in the plane, where the worst case ratio tends to infinity. In these examples some dense point clusters have a big influence on the directions of the principal components, and the resulting PCA bounding boxes have much larger volumes than the minimal ones. To avoid the influence of such non-uniform distributions of the point sets, we consider PCA bounding boxes for continuous sets, especially for the convex hulls of point sets, obtaining several variants of continuous PCA. For those variants, we give lower bounds in arbitrary dimension, and upper bounds in $\mathbb{R}^2$ and $\mathbb{R}^3$. To obtain the lower bounds, we exploit a relation between the perfect reflective symmetry and the principal components of point sets. Each of the upper bounds in $\mathbb{R}^2$ and $\mathbb{R}^3$ is obtained from two parameterized bounds. The first bound is general for all bounding boxes, while to obtain the second bound, we exploit some of the properties of PCA, combining them with ideas from discrete geometry and integral calculus. The relation between the perfect reflective symmetry and the principal components of point sets, leads to a straightforward algorithm for computing the planes of symmetry of perfect and approximate reflective symmetric point sets. For the same purpose, we present an algorithm based on geometric hashing.

In vielen Anwendungen werden gro\ss e Punktmengen oder komplexe geometrische Formen zur Vereinfachung durch sie umh\"ullende Quader ersetzt (an Stelle dieses selten gebrauchten deutschen Begriffs wird im Weiteren der englische Terminus ``Bounding Box'' verwendet). Sie werden zum Beispiel in der Computergraphik f\"ur Datenstrukturen eingesetzt, die zum schnellen Rendering und zur Detektion von Kollisionen dienen. Weitere Anwendungen findet man in der Analyse von Formen oder in der Statistik zur Unterst\"utzung von Bereichsanfragen auf gro\ss en Stichprobenmegen. Eine sehr h\"aufig verwendete Heuristik zur Berechnung einer Bounding Box beruht auf der Hauptachsentransformation (oder Hauptkomponentenanalyse -- PCA). Wenn die Hauptachsen bekannt sind, kann man die entsprechend ausgerichtete Bounding Box leicht dadurch erhalten, dass die Minima und Maxima der Projektionen der Punktmenge auf die einzelnen Achsen be\\-stimmt werden. Somit kann man die PCA --Bounding--Box einer Menge von $n$ Punkten in $\R^{d}$ in linearer Zeit berechnen. Neben diesem Laufzeitvorteil sind die unproblema\\-tische Implementierung und die Erfahrung, dass die PCA--Bounding--Box in der Regel ein sehr kleines Volumen hat, weitere Argumente, die f\"ur den Einsatz der Hauptachsentransformation sprechen. In der vorliegenden Dissertation wird die Qualit\"at der PCA--Bounding--Box hinsichtlich des Ziels der Volumenminimierung untersucht. F\"ur das Volumenverh\"altnis zwischen PCA-- Bounding--Box und der optimalen Bounding Box (mit kleinstem Volumen) werden obere und untere Schranken nachgewiesen. Zuerst werden Beispiele von Punktmengen in der Ebene konstruiert, die aufzeigen, dass dieses Verh\"altnis sich im schlechtesten Fall nicht begrenzen l\"asst, also gegen Unendlich geht. Bei der Konstruktion dieser Mengen spielen dichte Punktcluster eine wichtige Rolle, welche die Hauptachsen in eine ung\"unstige Richtung zwingen. Um den Einfluss solcher ungleichm\"a\ss iger Punktverteilungen zu vermeiden, wird die Hauptachsentransformation auf stetige Punktmengen ausgedehnt, insbesondere auf die vollst\"andige konvexe H\"ulle einer Punktmenge oder auf den Rand der konvexen H\"ulle. F\"ur diese PCA--Varianten wird wieder das Volumenverh\"altnis zwischen PCA--Bounding--Box und der optimalen Bounding Box (im schlechtesten Fall) untersucht. Es werden untere Schranken f\"ur alle Dimensionen gezeigt und auf der anderen Seite f\"ur Punktmengen in $\R^{2}$ und $\R^{3}$ obere Schranken nachgewiesen. Zum Beweis der unteren Schranken wird ein Zusammenhang zwischen der Spiegelsymmetrie einer Punktmenge und ihren Hauptachsen verwendet. Die oberen Schranken werden jeweils durch zwei parametrisierte obere Schrankenfunktionen gewonnen. Dabei ist die erste Schrankenfunktion allgemein f\"ur jede Bounding Box g\"ultig, w\"ahrend die zweite die speziellen PCA--Eigenschaften verwendet und diese mit Ideen und Hilfsmitteln aus Geometrie und Integralrechnung kombiniert. Der erw\"ahnte Zusammenhang zwischen Spiegelsymmetrie und Hauptachsen kann leicht in einen Algorithmus \"uberf\"uhrt werden, mit dem untersucht werden kann, ob eine Punktmenge spiegelsymmetrisch oder n\"ahe\\-rungs\\-weise spiegelsymmetrisch ist. F\"ur diese Problemsstellung wird ein wei\\-te\\-rer Algorithmus vorgestellt, der auf geometrischem Hashing basiert.