article

Bounds on the quality of the PCA bounding boxes

Authors:

Darko Dimitrov,

Christian Knauer,

Klaus Kriegel,

Günter RoteAuthors Info & Claims

Computational Geometry: Theory and Applications, Volume 42, Issue 8

Pages 772 - 789

https://doi.org/10.1016/j.comgeo.2008.02.007

Published: 01 October 2009 Publication History

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 quite well approximate the minimum-volume bounding boxes. We present examples of discrete points sets in the plane, showing that the worst case ratio of the volume of the PCA bounding box and the volume of the minimum-volume bounding box tends to infinity. Thus, we concentrate our attention on PCA bounding boxes for continuous sets, especially for the convex hull of a point set. Here, we contribute lower bounds on the approximation factor of PCA bounding boxes of convex sets in arbitrary dimension, and upper bounds in R^2 and R^3.

References

[1]

Barequet, G., Chazelle, B., Guibas, L.J., Mitchell, J.S.B. and Tal, A., Boxtree: A hierarchical representation for surfaces in 3D. Computer Graphics Forum. v15. 387-396.

Google Scholar

[2]

Barequet, G. and Har-Peled, S., Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms. v38 i1. 91-109.

Crossref

Google Scholar

[3]

N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger, The R∗-tree: An efficient and robust access method for points and rectangles, in: ACM SIGMOD Int. Conf. on Manag. of Data, 1990, pp. 322--331

Digital Library

Google Scholar

[4]

Gottschalk, S., Lin, M.C. and Manocha, D., OBBTree: A hierarchical structure for rapid interference detection. Computer Graphics. v30. 171-180.

Crossref

Google Scholar

[5]

Grünbaum, B., Partitions of mass-distributions and convex bodies by hyperplanes. Pacific J. Math. v10. 1257-1261.

Google Scholar

[6]

Jolliffe, I., Principal Component Analysis. 2002. 2nd ed. Springer-Verlag, New York.

Google Scholar

[7]

Kharaghani, H. and Tayfeh-Rezaie, B., A Hadamard matrix of order 428. J. Combin. Designs. v13. 435-440.

Google Scholar

[8]

Lahanas, M., Kemmerer, T., Milickovic, N., Karouzakis, D.B.K. and Zamboglou, N., Optimized bounding boxes for three-dimensional treatment planning in brachytherapy. Med. Phys. v27. 2333-2342.

Crossref

Google Scholar

[9]

Mityagin, B., Two inequalities for volumes of convex bodies. Math. Notes. v5. 61-65.

Google Scholar

[10]

O'Rourke, J., Finding minimal enclosing boxes. Int. J. Comp. Info. Sci. v14. 183-199.

Crossref

Google Scholar

[11]

N. Roussopoulos, D. Leifker, Direct spatial search on pictorial databases using packed R-trees, in: ACM SIGMOD, 1985, pp. 17--31

Digital Library

Google Scholar

[12]

Sellis, T., Roussopoulos, N. and Faloutsos, C., The R+-tree: A dynamic index for multidimensional objects. VLDB J. 507-518.

Crossref

Google Scholar

[13]

G. Toussaint, Solving geometric problems with the rotating calipers, in: IEEE MELECON, May 1983

Google Scholar

[14]

D.V. Vranić, D. Saupe, J. Richter, Tools for 3D-object retrieval: Karhunen--Loeve transform and spherical harmonics, in: IEEE 2001 Workshop Multimedia Signal Processing, 2001, pp. 293--298

Google Scholar

Cited By

View all

Nguyen LLe TLe HNgo D(2024)Post-processing Workflow for 3D Vietnamese Historical Printing Woodblocks Restoration from 2D printsProceedings of the 2024 9th International Conference on Intelligent Information Technology10.1145/3654522.3654574(203-208)Online publication date: 23-Feb-2024
https://dl.acm.org/doi/10.1145/3654522.3654574
Hahner SIza-Teran RGarcke J(2020)Analysis and Prediction of Deforming 3D Shapes Using Oriented Bounding Boxes and LSTM AutoencodersArtificial Neural Networks and Machine Learning – ICANN 202010.1007/978-3-030-61609-0_23(284-296)Online publication date: 15-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-61609-0_23
Zhou YSaitou K(2018)Gradient-based multi-component topology optimization for stamped sheet metal assemblies (MTO-S)Structural and Multidisciplinary Optimization10.1007/s00158-017-1878-y58:1(83-94)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00158-017-1878-y
Show More Cited By

Bounds on the quality of the PCA bounding boxes
1. Computing methodologies
  1. Computer graphics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

New upper bounds on the quality of the PCA bounding boxes in r² and r³
SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

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 quite well approximate the ...
Analyzing bounding boxes for object intersection

Heuristics that exploit bouning boxes are common in algorithms for rendering, modeling, and animation. While experience has shown that bounding boxes improve the performance of these algorithms in practice, the previous theoretical analysis has concluded ...
Recursive X-Y cut using bounding boxes of connected components
ICDAR '95: Proceedings of the Third International Conference on Document Analysis and Recognition (Volume 2) - Volume 2

A top-down page segmentation technique known as the recursive X-Y cut decomposes a document image recursively into a set of rectangular blocks. This paper proposes that the recursive X-Y cut be implemented using bounding boxes of connected components of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Geometry: Theory and Applications

Computational Geometry: Theory and Applications Volume 42, Issue 8

October, 2009

92 pages

ISSN:0925-7721

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 October 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nguyen LLe TLe HNgo D(2024)Post-processing Workflow for 3D Vietnamese Historical Printing Woodblocks Restoration from 2D printsProceedings of the 2024 9th International Conference on Intelligent Information Technology10.1145/3654522.3654574(203-208)Online publication date: 23-Feb-2024
https://dl.acm.org/doi/10.1145/3654522.3654574
Hahner SIza-Teran RGarcke J(2020)Analysis and Prediction of Deforming 3D Shapes Using Oriented Bounding Boxes and LSTM AutoencodersArtificial Neural Networks and Machine Learning – ICANN 202010.1007/978-3-030-61609-0_23(284-296)Online publication date: 15-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-61609-0_23
Zhou YSaitou K(2018)Gradient-based multi-component topology optimization for stamped sheet metal assemblies (MTO-S)Structural and Multidisciplinary Optimization10.1007/s00158-017-1878-y58:1(83-94)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00158-017-1878-y
Chang CGorissen BMelchior S(2011)Fast oriented bounding box optimization on the rotation group SO(3,ℝ)ACM Transactions on Graphics10.1145/2019627.201964130:5(1-16)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2019627.2019641

Abstract

References

Cited By

Recommendations

New upper bounds on the quality of the PCA bounding boxes in r2 and r3

Analyzing bounding boxes for object intersection

Recursive X-Y cut using bounding boxes of connected components

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations

New upper bounds on the quality of the PCA bounding boxes in r² and r³