Published: 2015-11-24
ISBN: 978-91-7685-855-4
ISSN: 1650-3686 (print), 1650-3740 (online)
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.
[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
