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

# New upper bounds on the quality of PCA bounding boxes in
*R*^{2} and *R*^{3}

*In: Abstracts of the 23rd European Workshop on Computational
Geometry,
Graz, March 2007, pp. 122-125.*
*In:
Proceedings of the 23rd Annual Symposium on Computational
Geometry, Gyeongju, South Korea, June 6-8, 2007. Association for
Computing
Machinery, 2007, pp. 275-283.*
*full version, submitted for publication.*

### 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.
There are examples of discrete points sets in the plane showing that
the
worst case ratio tends to infinity. Thus, we consider PCA bounding
boxes for
continuous sets, especially for the convex hull of a point set. We
contribute
new upper bounds on the approximation factor of PCA bounding boxes of
convex
sets in *R*^{2} and *R*^{3}.

Last update: March 27, 2007.