Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter
1. New upper bounds on the quality of PCA bounding boxes in
R2 and R3
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. doi:10.1145/1247069.1247119
2. 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.
3. Bounds on the quality of the PCA bounding boxes
Computational Geometry, Theory and
Applications 42 (2009), pp. 772–789.
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: January 18, 2008.