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
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.
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.
Last update: January 18, 2008.