More Web Proxy on the site http://driver.im/

research-article

Parallel computation of optimal enclosing balls by iterative orthant scan

Authors:

Thomas Larsson,

Gabriele Capannini,

Linus KällbergAuthors Info & Claims

Computers and Graphics, Volume 56, Issue C

Pages 1 - 10

https://doi.org/10.1016/j.cag.2016.01.003

Published: 01 May 2016 Publication History

Abstract

We propose an algorithm for computing the exact minimum enclosing ball of large point sets in general dimensions. It aims to reduce the number of passes by retrieving a well-balanced set of outliers in each linear search through the input by decomposing the space into orthants. The experimental evidence indicates that the convergence rate in terms of the required number of linear passes is superior compared to previous exact methods, and substantially faster execution times are observed in dimensions d 16 . In the important three-dimensional case, the execution times indicate real-time performance. Furthermore, we show how the algorithm can be adapted for parallel execution on both CPU and GPU architectures using OpenMP, AVX, and CUDA. For large datasets, our CUDA solution is superior. For example, the benchmark results show that optimal bounding spheres for inputs with tens of millions of points can be computed in just a few milliseconds. Graphical abstractDisplay Omitted HighlightsA fast minimum enclosing ball algorithm for general dimensions.An effective heuristic drastically reducing the number of algorithmic steps.Exhaustive study of parallelization opportunities for different platforms.Real-time exact bounding sphere computation in 3D.

References

[1]

G. Bradshaw, C. O'Sullivan, Adaptive medial-axis approximation for sphere-tree construction, ACM Trans Graph, 23 (2004) 1-26.

Digital Library

[2]

J. Elzinga, D. Hearn, The minimum covering sphere problem, Manag Sci, 19 (1972) 96-104.

Digital Library

[3]

Gottschalk S, Lin MC, Manocha D. OBBTree: a hierarchical structure for rapid interference detection. In: Proceedings of the 23rd annual conference on computer graphics and interactive techniques; 1996. p. 171-80.

Digital Library

[4]

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. p. 369-80.

Digital Library

[5]

Larsson T. Adaptive bounding volume hierarchies for efficient collision queries Ph.D. thesis. Mälardalen University, Sweden: School of Innovation, Design and Engineering; 2009.

[6]

J.W. Chang, W. Wang, M.S. Kim, Efficient collision detection using a dual OBB-sphere bounding volume hierarchy, Comput Aided Des, 42 (2010) 50-57.

Digital Library

[7]

H. Weghorst, G. Hooper, D.P. Greenberg, Improved computational methods for ray tracing, ACM Trans Graph, 3 (1984) 52-69.

Digital Library

[8]

Zarrabi-Zadeh H, Chan TM. A simple streaming algorithm for minimum enclosing balls. In: Proceedings of the 18th Canadian conference on computational geometry; 2006. p. 139-42.

[9]

J. Ritter, Graphics Gems, in: An efficient bounding sphere, Academic Press, San Diego, CA, USA, 1990, pp. 301-303.

[10]

F.P. Preparata, M.I. Shamos, Computational geometry: an introduction, Springer-Verlag, New York, 1985.

[11]

Welzl E. Smallest enclosing disks (balls and ellipsoids). In: Maurer H, editor. New results and new trends in computer science. Lecture notes in computer science. vol. 555. Berlin Heidelberg: Springer; 1991. p. 359-70.

[12]

Gärtner B. Fast and robust smallest enclosing balls. In: Proceedings of the seventh annual European symposium on algorithms. London: Springer-Verlag; 1999. p. 325-38.

[13]

Larsson T. Exact bounding spheres by iterative octant scan. In: Proceedings of SIGRAD 2015; 2015. p. 9-12.

[14]

J.J. Sylvester, A question in the geometry of situation, Q J Pure Appl Math, 1 (1857) 79.

[15]

J.J. Sylvester, On Poncelet's approximate linear valuation of surd forms, Philos Mag Ser 4, 20 (1860) 203-222.

[16]

Chrystal G. On the problem to construct the minimum circle enclosing n given points in a plane. In: Proceedings of the Edinburgh Mathematical Society, third meeting; 1885. p. 30-3.

[17]

R.K. Chakraborty, P.K. Chaudhuri, Letter to the editornote on geometrical solution for some minimax location problems, Transp Sci, 15 (1981) 164-166.

Digital Library

[18]

Shamos MI, Hoey D. Closest-point problems. In: Proceedings of the 16th annual symposium on foundations of computer science; 1975. p. 151-62.

Digital Library

[19]

Preparata FP. Minimum spanning circle. In: Preparata FP, editor. Steps into computational geometry. Urbana, Illinois: University of Illinois; 1977. p. 3-5.

[20]

S. Skyum, A simple algorithm for computing the smallest enclosing circle, Inf Process Lett, 37 (1991) 121-125.

[21]

Hopp TH, Reeve CP. An algorithm for computing the minimum covering sphere in any dimension. Tech. Rep. NISTIR 5831; National Institute of Standards and Technology; 1996.

[22]

Fischer K, Gärtner B, Kutz M. Fast smallest-enclosing-ball computation in high dimensions. In: Proceedings of the 11th annual European symposium on algorithms (ESA). Springer-Berlin Heidelberg: Springer-Verlag; 2003. p. 630-41.

[23]

J. Elzinga, D. Hearn, Geometrical solutions for some minimax location problems, Transp Sci, 6 (1972) 379-394.

Digital Library

[24]

N. Megiddo, Linear-time algorithms for linear programming in R 3 and related problems, SIAM J Comput, 12 (1983) 759-776.

[25]

N. Megiddo, Linear programming in linear time when the dimension is fixed, J ACM (JACM), 31 (1984) 114-127.

[26]

J. Matoušek, M. Sharir, E. Welzl, A subexponential bound for linear programming, Algorithmica, 16 (1996) 498-516.

[27]

R. Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete Comput Geom, 6 (1991) 423-434.

Digital Library

[28]

B. Gärtner, A subexponential algorithm for abstract optimization problems, SIAM J Comput, 24 (1995) 1018-1035.

Digital Library

[29]

M. Ba¿doiu, K.L. Clarkson, Optimal core-sets for balls, Comput Geom: Theory Appl, 40 (2008) 14-22.

Digital Library

[30]

Ba¿doiu M, Clarkson KL. Smaller core-sets for balls. In: Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms; 2003. p. 801-2.

[31]

E.A. Yildirim, Two algorithms for the minimum enclosing ball problem, SIAM J Optim, 19 (2008) 1368-1391.

Digital Library

[32]

P. Kumar, J.S.B. Mitchell, E.A. Yildirim, Approximate minimum enclosing balls in high dimensions using core-sets, J Exp Algorithm (2003) 8.

[33]

F. Nielsen, R. Nock, Approximating smallest enclosing balls with applications to machine learning, Int J Comput Geom Appl, 19 (2009) 389-414.

[34]

T. Larsson, L. Källberg, Fast and robust approximation of smallest enclosing balls in arbitrary dimensions, Comput Graph Forum, 32 (2013) 93-101.

[35]

Gärtner B, Welzl E. Random sampling in geometric optimization: New insights and applications. In: Proceedings of the sixteenth annual symposium on computational geometry. SCG'00; New York, NY, USA: ACM; 2000. p. 91-9.

Digital Library

[36]

S. Har-Peled, Geometric approximation algorithms, American Mathematical Society, Boston, MA, USA, 2011.

Digital Library

[37]

P. Agarwal, R. Sharathkumar, Streaming algorithms for extent problems in high dimensions, Algorithmica, 72 (2015) 83-98.

Digital Library

[38]

T.M. Chan, V. Pathak, Streaming and dynamic algorithms for minimum enclosing balls in high dimensions, Comput Geom: Theory Appl, 47 (2014) 240-247.

Digital Library

[39]

I.W. Tsang, J.T. Kwok, P.M. Cheung, Core vector machines, J Mach Learn Res, 6 (2005) 363-392.

Digital Library

[40]

Z. Drezner, Continuous center problems, in: Foundations of location analysis; International series in operations research & management science, vol. 155, Springer, 2011, pp. 63-78.

[41]

N. Kurd, M. Chowdhury, E. Burton, T. Thomas, C. Mozak, B. Boswell, Haswell, IEEE J Solid-State Circuits, 50 (2015) 49-58.

[42]

L. Dagum, R. Menon, OpenMP, IEEE Comput Sci Eng, 5 (1998) 46-55.

[43]

B. Chapman, G. Jost, R. van der Pas, Using OpenMP: portable shared memory parallel programming, The MIT Press, 1987.

[44]

Capannini G, Baraglia R, Silvestri F, Maria Nardini F. Effective data access patterns on massively parallel processors. In: High-performance computing on complex environments. Hoboken, NJ, USA: John Wiley & Sons, Inc.; 2014. p. 115-34.

[45]

Terdiman P. Radix sort revisited. Online paper; 2000. {http://www.codercorner.com/RadixSortRevisited.htm}.

[46]

D. Tarjan, K. Skadron, P. Micikevicius, The art of performance tuning for CUDA and many core architectures, Birds-of-a-feather session at SC'09 (2009).

[47]

S. Cook, CUDA programming: a developer's guide to parallel computing with GPUs, Morgan Kaufmann, 2012.

[48]

Davidson A, Owens J. Toward techniques for auto-tuning GPU algorithms. In: Applied parallel and scientific computing. Lecture notes in computer science. vol. 7134. Berlin, Heidelberg: Springer; 2012. p. 110-19.

[49]

L. Källberg, T. Larsson, Faster approximation of minimum enclosing balls by distance filtering and GPU parallelization, J Graph Tools, 17 (2013) 67-84.

[50]

Che S, Boyer M, Meng J, Tarjan D, Sheaffer JW, Lee SH, et al. Rodinia: a benchmark suite for heterogeneous computing. In: Proceedings of the IEEE international symposium on workload characterization (IISWC); 2009. p. 44-54.

Digital Library

[51]

Micikevicius P. GPU performance analysis and optimization. GPU Technology Conference; 2012.

[52]

S.D. Ahipasaog¿lu¿, E.A. Yildirim, Identification and elimination of interior points for the minimum enclosing ball problem, SIAM J Optim, 19 (2008) 1392-1396.

Digital Library

[53]

L. Källberg, T. Larsson, Improved pruning of large data sets for the minimum enclosing ball problem, Graph Models, 76 (2014) 609-619.

Digital Library

[54]

Källberg L, Shellshear E, Larsson, T. An external memory algorithm for the minimum enclosing ball problem. In: Proceedings of the 11th joint conference on computer vision, imaging and computer graphics theory and applications (VISIGRAPP 2016). 1: GRAPP, 2016. p. 81-88. ISBN: 978-989-758-175-5.

Digital Library

Cited By

Wang YYu SDhulipala LGu YShun JLee JAgrawal KSpear M(2022)ParGeoProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508429(450-452)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508429
Cavaleiro MAlizadeh F(2021)A dual simplex-type algorithm for the smallest enclosing ball of ballsComputational Optimization and Applications10.1007/s10589-021-00283-679:3(767-787)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s10589-021-00283-6
Peters CDoggett MKjelldahl L(2016)Foreword to special section on SIGGRAD 2015Computers and Graphics10.1016/j.cag.2016.04.00157:C(A1-A2)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.cag.2016.04.001

Recommendations

Approximate minimum enclosing balls in high dimensions using core-sets

We study the minimum enclosing ball (MEB) problem for sets of points or balls in high dimensions. Using techniques of second-order cone programming and "core-sets", we have developed (1 + ε)-approximation algorithms that perform well in practice, ...
On approximating the smallest enclosing Bregman Balls
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

We present a generalization of Bǎdoiu and Clarkson's algorithm [3] for computing a (1+ε)-approximation of the smallest enclosing ball of a point set equipped with a Bregman divergence as a distortion measure.
A branch-and-bound method for the minimum k−enclosing ball problem
Abstract
The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Graphics

Computers and Graphics Volume 56, Issue C

May 2016

63 pages

ISSN:0097-8493

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 May 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang YYu SDhulipala LGu YShun JLee JAgrawal KSpear M(2022)ParGeoProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508429(450-452)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508429
Cavaleiro MAlizadeh F(2021)A dual simplex-type algorithm for the smallest enclosing ball of ballsComputational Optimization and Applications10.1007/s10589-021-00283-679:3(767-787)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s10589-021-00283-6
Peters CDoggett MKjelldahl L(2016)Foreword to special section on SIGGRAD 2015Computers and Graphics10.1016/j.cag.2016.04.00157:C(A1-A2)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.cag.2016.04.001

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents