Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter Rote:

1. On the bounding boxes obtained by principal component analysis

In: Abstracts of the 22nd European Workshop on Computational Geometry, Delphi, March 2006, pp. 193-196. (preliminary version with partial results)

2. Upper and lower bounds on the quality of the PCA bounding boxes

In: WSCG'2007, Prof. 15th Int. Conf. in Central Europe on Computer Graphics, Visualization and Computer Vision, Plzen, Czech Republic, January 29 - February 1, 2007, Editors: Jarek Rossignac and Vaclav Skala, pp. 185-192.

Abstract

Principal component analysis (PCA) is commonly used to compute a bounding box of a point set in R^d. The popularity of this heuristic lies in its speed, easy implementation and in the fact that usually, PCA bounding boxes approximate the minimum-volume bounding boxes quite well. In this paper we give a lower bound on the approximation factor of PCA bounding boxes of convex polytopes in arbitrary dimension, and an upper bound on the approximation factor of PCA bounding boxes of convex polygons in R².

pdf file

other papers about this subject

Last update: March 27, 2007.