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

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 Geometry, 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. doi:10.1016/j.comgeo.2008.02.007


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.

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 R2 and R3.

  pdf file (gzipped)
other papers about this subject
Last update: January 18, 2008.