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 Rd. 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 R2.
Last update: March 27, 2007.