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.
Abstract
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 approximation with specified precision within much less time comparing with present algorithms.
With the new 1+ϵ approximation algorithm , A large case d=2048, n=128k, ϵ=10-6 can be solved in a few minutes, which has not been done with previous solvers.
1. Introduction
Also known as bounding sphere problem or Smallest Enclosing Ball problem, Minimal Enclosing Ball (MEB) problem is to find out the minimal enclosing ball for a given set of points P ⊂ ℝd. The MEB problem was well studied for its large number of applications, which include computational graphic, high dimensional data mining etc. See more reference in Fischer [1], or Kumar [2].
Data mining techniques such as clustering, nearest neighbor searching usually involves MEB problems in high dimensions, which become very time consuming or even impractical to be solved for traditional exact solver such as Welzl's method [3] or approach of Gärtner et al.
Ritter's solution [6] is an attempt for providing a bounding sphere. The fascinating thing of Ritter's approach is its simplicity of implementation and its short execution time. However, it provides only very coarse result with around 15% error. In comparison, the substitution provide results with 1%~2% error.
Bădoiu et al introduced an approach that apply Second Order Cone Programming (SOCP) on a subset of the data set (referred as core set) to get an approximate result, any point outside 1+ϵ approximation will be added into the core set until all points reside in the 1+ϵ approximation. This approach yield to a computational complexity of[Abbildung in dieser Leseprobe nicht enthalten][5]. Kumar et al improved this approach by solving the problem with incremental precision [2]. The result computational complexity is [Abbildung in dieser Leseprobe nicht enthalten].
Another noticeable contribution is the approach by Fischer et al. They proposed an exact solver with O(nd2) complexity [1].
These two algorithm are quite successful since they were proposed. However, alternative approaches to solve MEB problem can be even more efficient in practice.
Instead of using core-set, new approach maintains a expanding ball (referred as "Bubble") that is always smaller than MEB, and inflates it until its 1+ϵ ball contains all points. In each inflation, only one point is involved, so that the computation is very minimal. The algorithm is called Bouncing Bubble algorithm because during the inflating process, the bubble is moving around like bouncing among the points. With this new algorithm, MEB 1+ϵ approximation can be solved in[Abbildung in dieser Leseprobe nicht enthalten] .
This paper is organized in this way: the background of the problem and related work will be introduced in section 2. Some mathematic observations on the MEB problem will be discussed in section 3. Section 4 will present algorithms and some discussions on the behavior of the algorithms. In section 5, a more sophisticate algorithm to cope with arbitrary precision and exact solution is presented. And finally experimental results and conclusions will be given in section 6.
2. Related Works
In this section, some previous work will be briefly described. Since this is not a review paper, only most related works are listed here.
Ritter's bounding sphere
Ritter proposed a simple algorithm to find a "bounding sphere" around data set P . The algorithm can be described as follows:
1. Pick a point x from P , search a point y in P , which has the largest distance from x;
2. Search a point z in P , which has the largest distance from y. set up an initial ball B, with its centre as the midpoint of y and z, the radius as half of the distance between y and z;
3. If all points in P is within ball B, then we get a bounding sphere. Otherwise, let p be the point outside the ball, which has distance d from the boundary of B. Move the centre of B towards p by d/2, and increase radius by d/2 to get a new ball.
The beauty of Ritter's algorithm is its simplicity. With only 3 walks through the data set, it produce a reasonable small bounding sphere.
In brief, Ritter's algorithm tries to find a ball as large as possible (As shown in step 1,2, which was first introduced by Egecioglu and Kalantari in [7] ), and then enlarges it further more to cover all points in P . The final step ensure all points in P is enclosed by the given ball. In this paper, step 3 will be referred as "Ritter's enclosing approach", and will be used as final step for some proposed algorithms.
Bădoiu 's Core set based 1+ ϵ approximation
Core set was introduced by Bădoiu et al. The brief idea of the algorithm is to find a subset of the point set, and compute the MEB of the subset as a solution. It can be detailed as follows:
1. Pick a point x from P , search a point y in P , which has the largest distance from x;
2. Search a point z in P , which has the largest distance from y. Initial core set as {y,z} and set an initial ball B, with its centre as the midpoint of y and z, the radius as half of the distance between y and z;
3. If all points in P is within ball (1+ϵ) B, then we get a bounding 1+ϵ approximation. Otherwise, let p be the farthest point from the centre of B, add p into core set; Compute a new ball B to be MEB of the core set. Repeat step 3 until 1+ϵ approximation is obtained.
In fact, the first two steps are the same with which was used in Ritter's algorithm. In step 3, the author use SOCP to obtain MEB of core set.
Kumar's Core set based 1+ ϵ approximation
Kumar's improvement is to compute a core set start with coarse precision (say, 2kϵ), and then compute core set with 2k-1ϵ, and so on and so forth, until finally with precision ϵ. In this way, the size of core set is minimized and therefore computational complexity is also minimized. The result computational complexity is .
As we can see, since these 1+ϵ approximation requires choosing a subset of data and applying SOCP on it, the implementation become more complex.
3. Preliminary
This section discuss some basic geometry property of MEB problem and the property of a "Bubble".
Let's denote B(C, r) as a d-dimensional ball, where C ∈ℝd is its centre and r∈ℝ+ is its radius. For simplicity reason, we denote Bi as B(C i, ri) when there would be no confusion.
Let B(C *,r*) be the MEB of point[Abbildung in dieser Leseprobe nicht enthalten] As proved in [3], B(C *,r*) exists and is unique.
We call ball B(C, r) a "Bubble" when it satisfy the inequality [Abbildung in dieser Leseprobe nicht enthalten]See Fig 2.
illustration not visible in this excerpt
Fig 2 Definition of a bubble
A bubble is basically a ball that the MEB could cover at least half of it. According to the definition, any point p∈ P is a bubble with its radius equals to zero. MEB itself is also a bubble.
Lemma 1. Let[Abbildung in dieser Leseprobe nicht enthalten] be two points inside[Abbildung in dieser Leseprobe nicht enthalten]Let B(C, r) be a ball where C is the midpoint of P 1 P 2, , then B(C, r) is a bubble.
illustration not visible in this excerpt
Fig 3 Bubble construction from two points
Proof:
illustration not visible in this excerpt
One of the following inequalities must be true
Thus
illustration not visible in this excerpt
Recall that the first two steps of Ritter's algorithm is to find a big enough ball, which is actually to find a big enough bubble.
As an extension to Lemma 1, we have:
Lemma 2. Let S be a subset of P , S ⊂ P , B(C, r) is the MEB of S, then B(C, r) is a bubble of P.
Proof:
According to lemma 3.1 in Kumar 2003, let hyperplane L pass through C and be perpendicular to C*C, there exists a point p ∈ S , p resides on the half space farther from C *. Thus
This lemma shows that core set based algorithm can be considered as a variant of Bouncing bubble algorithm which construct inflating bubble in a different fashion.
Lemma 3. Let B(C i, ri) be a set of bubbles, 1≤i≤n, then B(C, r) is also a bubble, where [Abbildung in dieser Leseprobe nicht enthalten]
Proof:
illustration not visible in this excerpt
Let
Thus it's obvious that
illustration not visible in this excerpt
This lemma shows that an affine combination of bubbles is also a bubble. This lemma is listed here only for completeness, it's not referenced in the rest of the paper.
[...]
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X.