Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter
New upper bounds on the quality of PCA bounding boxes in
R2 and R3
- In: Abstracts of the 23rd European Workshop on Computational
Graz, March 2007, pp. 122-125.
Proceedings of the 23rd Annual Symposium on Computational
Geometry, Gyeongju, South Korea, June 6-8, 2007. Association for
Machinery, 2007, pp. 275-283.
- full version, submitted for publication.
Principal component analysis (PCA) is commonly used to compute a
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
approximate the minimum-volume bounding boxes quite well.
There are examples of discrete points sets in the plane showing that
worst case ratio tends to infinity. Thus, we consider PCA bounding
continuous sets, especially for the convex hull of a point set. We
new upper bounds on the approximation factor of PCA bounding boxes of
sets in R2 and R3.
Last update: March 27, 2007.