Article

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

Authors:

Darko Dimitrov,

Christian Knauer,

Klaus Kriegel,

G. RoteAuthors Info & Claims

SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

Pages 275 - 283

https://doi.org/10.1145/1247069.1247119

Published: 06 June 2007 Publication History

Get Access

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.Since there are examples of discrete points sets in the plane, showing that the worst case ratio of the volume ofthe PCA bounding box and the volume of the minimum-volume bounding box tends to infinity,we consider PCA bounding boxes for continuous sets, especially for the convex hull of a point set. Here, we contributenew upper bounds on the approximation factor of PCA bounding boxesof convex sets in R² and R³.

References

[1]

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

Crossref

Google Scholar

[2]

G. Barequet and S. Har-Peled. Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. In 10th ACM-SIAM Sympos. Discrete Algorithms, pages 82--91, 1999.

Digital Library

Google Scholar

[3]

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

Digital Library

Google Scholar

[4]

D. Dimitrov, C. Knauer, K. Kriegel, and G. Rote. Upper and lower bounds on the quality of the PCA bounding boxes. In International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision -- WSCG 2007, pages 185--192, 2007.

Google Scholar

[5]

S. Gottschalk, M.C. Lin, and D. Manocha. OBBTree: A hierarchical structure for rapid interference detection. In SIGGRAPH 1996, pages 171--180, 1996.

Digital Library

Google Scholar

[6]

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

Google Scholar

[7]

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

Google Scholar

[8]

M. Lahanas, T. Kemmerer, N. Milickovic, D.B. KKarouzakis, and N. Zamboglou. Optimized bounding boxes for three--dimensional treatment planning in brachytherapy. In Med. Phys. 27, pages 2333--2342, 2000.

Crossref

Google Scholar

[9]

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

Crossref

Google Scholar

[10]

J. O'Rourke. Finding minimal enclosing boxes. In Int. J. Comp. Info. Sci. 14, pages 183--199, 1985.

Crossref

Google Scholar

[11]

N. Roussopoulos and D. Leifker. Direct spatial search on pictorial databases using packed R-trees. In ACM SIGMOD, pages 17--31, 1985.

Digital Library

Google Scholar

[12]

T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-tree: A dynamic index for multidimensional objects. In 13th VLDB Conference, pages 507--518, 1987.

Digital Library

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, and J. Richter. Tools for 3D-object retrieval: Karhunen-Loeve transform and spherical harmonics. In IEEE 2001 Workshop Multimedia Signal Processing, pages 293--298, 2001.

Crossref

Google Scholar

Cited By

View all

Chelishchev PSørby K(2020)Estimation of minimum volume of bounding box for geometrical metrologyInternational Journal of Metrology and Quality Engineering10.1051/ijmqe/202000711(9)Online publication date: 22-Oct-2020
https://doi.org/10.1051/ijmqe/2020007
Shen HHuang ZCao JZhou X(2009)High-dimensional indexing with oriented cluster representation for multimedia databasesProceedings of the 2009 IEEE international conference on Multimedia and Expo10.5555/1698924.1699335(1628-1631)Online publication date: 28-Jun-2009
https://dl.acm.org/doi/10.5555/1698924.1699335
Shen HHuang ZCao JZhou X(2009)High-dimensional indexing with oriented cluster representation for multimedia databases2009 IEEE International Conference on Multimedia and Expo10.1109/ICME.2009.5202831(1628-1631)Online publication date: Jun-2009
https://doi.org/10.1109/ICME.2009.5202831

Index Terms

New upper bounds on the quality of the PCA bounding boxes in r² and r³
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Bounds on the quality of the PCA bounding boxes

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

Information & Contributors

Information

Published In

SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

June 2007

404 pages

ISBN:9781595937056

DOI:10.1145/1247069

Program Chair:
Jeff Erickson
University of Illinois, Urbana-Champaign, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
202
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chelishchev PSørby K(2020)Estimation of minimum volume of bounding box for geometrical metrologyInternational Journal of Metrology and Quality Engineering10.1051/ijmqe/202000711(9)Online publication date: 22-Oct-2020
https://doi.org/10.1051/ijmqe/2020007
Shen HHuang ZCao JZhou X(2009)High-dimensional indexing with oriented cluster representation for multimedia databasesProceedings of the 2009 IEEE international conference on Multimedia and Expo10.5555/1698924.1699335(1628-1631)Online publication date: 28-Jun-2009
https://dl.acm.org/doi/10.5555/1698924.1699335
Shen HHuang ZCao JZhou X(2009)High-dimensional indexing with oriented cluster representation for multimedia databases2009 IEEE International Conference on Multimedia and Expo10.1109/ICME.2009.5202831(1628-1631)Online publication date: Jun-2009
https://doi.org/10.1109/ICME.2009.5202831

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Bounds on the quality of the PCA bounding boxes

Analyzing bounding boxes for object intersection

Recursive X-Y cut using bounding boxes of connected components

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations