In this paper, a new algorithm for solving MEB problem is proposed based on new understandings on the geometry property of minimal enclosing ball problem. A substitution of Ritter's algorithm is proposed to get approximate results with higher precision, and a 1+ϵ approximation algorithm is presented to get the approximation with specified precision within much less time comparing with present algorithms.
Like Ritter's algorithm, this algorithm iterates over all points and increase the radius gradually. However, the algorithm does not try to cover all seen points in each step, instead, it will create a new ball (or circle in 2D case) to just touch the new point and cover half of the existing ball. This approach makes sure that the new ball is always increasing in its size and still be smaller than the optimal ball. And finally, a Ritter's algorithm is applied to ensure every point is covered.
The result is an approximate solution to the MEB problem. The radius is usually just slightly bigger than the optimal solution (around 1%) instead (5~20% with Ritter's algorithm).
This paper also explained how to compute 1+ϵ approximation solution, where ϵ is specified to a given precision.
Inhaltsverzeichnis (Table of Contents)
- Introduction
- Related Works
- Ritter's bounding sphere
- Bădoiu's Core set based 1+€ approximation
- Kumar's Core set based 1+€ approximation
- Preliminary
- Algorithms
- Results
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
This paper introduces a new algorithm, the "Bouncing Bubble" algorithm, for solving the Minimal Enclosing Ball (MEB) problem, which involves finding the smallest sphere that encloses a given set of points. The algorithm aims to achieve a high level of precision in a significantly reduced time frame compared to existing methods.
- Efficient MEB algorithm
- Geometric properties of MEB
- Comparison with existing methods
- 1+€ approximation algorithm
- Practical applications in data mining and computational graphics
Zusammenfassung der Kapitel (Chapter Summaries)
- Introduction: This chapter introduces the MEB problem and highlights its importance in various fields, emphasizing the limitations of existing methods, particularly for high-dimensional data sets. The paper proposes a new approach, the "Bouncing Bubble" algorithm, as a more efficient solution.
- Related Works: This section briefly describes previous research efforts related to the MEB problem, focusing on Ritter's bounding sphere algorithm, Bădoiu's core-set-based approximation method, and Kumar's improvement on Bădoiu's approach. The discussion emphasizes the strengths and weaknesses of these existing methods.
- Preliminary: This chapter delves into fundamental geometric properties of the MEB problem, defining and explaining the concept of a "bubble" within the context of MEB. The discussion includes lemmas and proofs to establish the mathematical foundation for the proposed algorithm.
Schlüsselwörter (Keywords)
Minimal Enclosing Ball, Bounding Sphere, Smallest Enclosing Ball, Bouncing Bubble algorithm, 1+€ approximation, Core-set, Ritter's algorithm, Geometric properties, Data mining, Computational graphics.
- Citation du texte
- Bo Tian (Auteur), 2012, Bouncing Bubble: A fast algorithm for Minimal Enclosing Ball problem, Munich, GRIN Verlag, https://www.grin.com/document/204869
