Bouncing Bubble: A fast algorithm for Minimal Enclosing Ball problem

Scientific Essay 2012 18 Pages

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 pS , 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.

[...]

Pages
18
Year
2012
ISBN (eBook)
9783656326663
ISBN (Book)
9783656326991
File size
1.5 MB
Language
English
Catalog Number
v204869