Article | Proceedings of SIGRAD 2015, June 1st and 2nd, Stockholm, Sweden | Exact Bounding Spheres by Iterative Octant Scan
Göm menyn

Title:
Exact Bounding Spheres by Iterative Octant Scan
Author:
Thomas Larsson: School of Innovation, Design and Engineering, Mälardalen University, Sweden
Download:
Full text (pdf)
Year:
2015
Conference:
Proceedings of SIGRAD 2015, June 1st and 2nd, Stockholm, Sweden
Issue:
120
Article no.:
003
Pages:
9-12
No. of pages:
4
Publication type:
Abstract and Fulltext
Published:
2015-11-24
ISBN:
978-91-7685-855-4
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press, Linköpings universitet


Export in BibTex, RIS or text

We propose an exact minimum bounding sphere algorithm for large point sets in low dimensions. It aims to reduce the number of required passes by retrieving a well-balanced set of outliers in each linear search through the input. The behaviour of the algorithm is mainly studied in the important three-dimensional case. The experimental evidence indicates that the convergence rate is superior compared to previous exact methods, which effectively results in up to three times as fast execution times. Furthermore, the run times are not far behind simple 2-pass constant approximation heuristics.

Keywords: Bounding spheres; computational geometry; geometric algorithms

Proceedings of SIGRAD 2015, June 1st and 2nd, Stockholm, Sweden

Author:
Thomas Larsson
Title:
Exact Bounding Spheres by Iterative Octant Scan
References:

[BO04] BRADSHAW G., O’SULLIVAN C.: Adaptive medial-axis approximation for sphere-tree construction. ACM Transactions on Graphics 23, 1 (Jan. 2004), 1–26. 1


[CWK10] CHANG J.-W., WANG W., KIM M.-S.: Efficient collision detection using a dual OBB-sphere bounding volume hierarchy. Computer Aided Design 42, 1 (2010), 50–57. 1


[EH72] ELZINGA J., HEARN D.: The minimum covering sphere problem. Management Science 19, 1 (1972), 96–104. 1


[FGK03] FISCHER K., GÄRTNER B., KUTZ M.: Fast smallestenclosing-ball computation in high dimensions. In In Proceedings of the 11th Annual European Symposium on Algorithms (ESA) (2003), Springer-Verlag, pp. 630–641. 1


[Gär99] GÄRTNER B.: Fast and robust smallest enclosing balls. In Proceedings of the 7th Annual European Symposium on Algorithms (1999), Springer-Verlag, pp. 325–338. 1, 2, 3


[GLM96] GOTTSCHALK S., LIN M. C., MANOCHA D.: OBBTree: a hierarchical structure for rapid interference detection. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques (1996), pp. 171–180. 1


[KL14] KÄLLBERG L., LARSSON T.: Accelerated computation of minimum enclosing balls by GPU parallelization and distance filtering. In Proceedings of SIGRAD 2014 (June 2014), pp. 57–65. 4


[KS97] KATAYAMA N., SATOH S.: The SR-tree: an index structure for high-dimensional nearest neighbor queries. In Proceedings of the 1997 ACM SIGMOD international conference on Management of data (1997), ACM, pp. 369–380. 1


[KWL10] KARLSSON M., WINBERG O., LARSSON T.: Parallel construction of bounding volumes. In Proceedings of SIGRAD 2010 (November 2010), pp. 65–69. 4


[LAM09] LARSSON T., AKENINE-MÖLLER T.: Bounding volume hierarchies of slab cut balls. Computer Graphics Forum 28, 8 (2009), 2379–2395. 1


[Rit90] RITTER J.: An efficient bounding sphere. In Graphics Gems, Glassner A., (Ed.). Academic Press, 1990, pp. 301–303. 1, 3


[Wel91] WELZL E.: Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, Maurer H., (Ed.), vol. 555 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 1991, pp. 359–370. 1


[WHG84] WEGHORST H., HOOPER G., GREENBERG D. P.: Improved computational methods for ray tracing. ACM Transactions on Graphics 3, 1 (1984), 52–69. 1


[ZZC06] ZARRABI-ZADEH H., CHAN T. M.: A simple streaming algorithm for minimum enclosing balls. In Proceedings of the 18th Canadian Conference on Computational Geometry (2006), pp. 139–142. 1, 3

Proceedings of SIGRAD 2015, June 1st and 2nd, Stockholm, Sweden

Author:
Thomas Larsson
Title:
Exact Bounding Spheres by Iterative Octant Scan
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment


Responsible for this page: Peter Berkesand
Last updated: 2017-02-21