Jump to content

Smallest-circle problem: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
m →Steepest Descent Approach: Add missing brace
Revert to a version that doesn't stuff the article with bad algorithms and not even metion the good ones, per talk
Line 1: Line 1:
The '''1-center problem''' is a [[mathematical problem]], in which we are given a set of points and we must find a circle covering all these points such that the radius of the circle is minimized. It is a special case of the [[bounding sphere]] problem and the [[minimax facility location]] problem of [[combinatorial optimization]].
=1. Problem=


The problem can be solved in [[linear time]] via the [[prune and search]] strategy. <ref name="Lee">Lee, R. C. T. (2005). Introduction to the design and analysis of algorithms : a strategic approach. Singapore: McGraw-Hill p.9</ref>
The '''minimum covering circle problem''' is a [[mathematical problem]] of computing a smallest enclosing circle of a set S of given N points in R<sup>n</sup>, which was initially proposed by Sylvester in 1987 [18]. This problem is also called minimum covering circle problem [4]. In two dimensional space, the problem is a well known single facility location problem which locates a new facility to provide service to a number of customers or facilities [7]. We can formulate the minimum covering circle problem as the minimax programming problem:

<math> \min_{x\in R^n} \max_{x\in S} \|x-s\|</math>

The problem can be reduced to the following minimization problem:

<math>\min ~ r</math>

with subject to

<math>\|x-s\|\leq r</math>

<math>x\in R^n,~s\in S,</math>

where <math>r</math> can be seen as the radius of the smallest covering circle, or equivalently

<math>\min ~ r</math>

with subject to

<math>\|x-s\|+v_s=r,</math>

<math>v_s\geq 0,~x\in R^n,~s\in S.</math>

=2. Algorithms=

From here on we will consider the minimum covering circle problem in two dimensional Euclidean space. Most of the geometric approaches for the problem look for points that lie on the boundary of the minimum circle and are based on the following simple facts:

- The minimum covering circle is unique.

- The minimum covering circle can be determined by at most three points in S which lie on the boundary of the circle. If it is determined by only two points, then the line segment joining those two points must be a diameter of the minimum circle. If it is determined by three points, then the triangle consists of those three points is not obtuse.

We note that, according to the above facts, the problem can be solved in <math>O(N^4)</math> by enumerating all the triples of the points in S under a model in which square roots are calculated in constant time.

==Chrystal-Peirce Algorithm==

The method described in Algorithm 1 first appeared in the papers by Sylvester and Chrystal. In the algorithm, the set <math>S_k</math> keeps two points that lie on the boundary of the current circle and the new covering circle is smaller than the previous one. The correctness of the algorithm is based on the facts mentioned earlier. It is not very difficult to see that, in Step 3, the new circle that passes through A, B and C is also a covering circle and smaller than the previous one.


'''Algorithm 1'''

Step 1. Set <math>k = 1</math>. Construct a circle that covers S and passes through two points, say A and B, in S. Find the center of the circle and denote by <math>O_k</math>.

Step 2. Set <math>S_k = \{A,B\}</math>. Find a point C that minimizes <math>\angle ADB</math> over <math>D\in S \setminus S_k</math>. If angle <math>\angle ADB</math> is obtuse, terminate the algorithm and the minimum circle has diameter AB.

Step 3. Set <math>k = k+1</math>. Construct the circle that passes through A, B and C, and denote its center by <math>O_k</math>. If triangle <math>\vartriangle ABC</math> is not obtuse, terminate the algorithm and <math>O^\ast = O_k</math>. Otherwise, <math>A = C</math> if angle <math>\angle BAC</math> is obtuse or <math>B = C </math> if angle <math>\angle ABC</math> is obtuse and go to Step 2.


Suppose that D and E are in S and lie in the other sides of chord AB. Since <math>\angle ACB \leq \angle ADB </math>, point D should also be in the new circle. We also know that <math>\angle ACB + \angle AEB \geq 180^\circ </math> since they both are covered by the current circle that passes through A and B. This implies that point E is also covered by the new circle that passes through A, B and C.

Chakraborty and Chaudhuri [1] proposes an e±cient selection of initial two points A and B in the first step of the Chrystal-Peirce algorithm which takes <math>O(N)</math>. At each iteration of the algorithm, A and B must be extreme points of the convex hull of S. If the number of extreme points is h, then Chrystal-Peirce algorithm runs in <math>O(hN)</math> in the worst case.

==Elzinga-Hearn Algorithm==


The following method described in Algorithm 2 is due to Elzinga and Hearn [4].

'''Algorithm 2'''

Step 1: Select any two points, A and B, in S.

Step 2: Construct a circle with the diameter AB. If the circle covers all the points terminate the algorithm. Otherwise, select a point C which is in outside of the circle.

Step 3: Construct the minimum covering circle for A, B and C. If the circle is defined by two points, then rename those two points by A and B, and go to Step 2.

Step 4: If the current circle defined by A, B and C covers all the points in S, terminate the algorithm. Otherwise, find a point D which is in outside of the current circle.

Step 5: Construct the minimum covering circle for A, B, C and D. If the minimum circle is defined by two points, then go to Step 2. Otherwise, go to Step 4.


Steps 1 and 2 each requires <math>O(N)</math> steps, therefore the worst case running time of the algorithm is <math>O(h^3N)</math>. However, Elzinga and Hearn [4] reported that computational results showed the algorithm to be O(N) empirically.


==Steepest Descent Approach==

Mathematical programming formulation of the minimum covering problem is convex. Therefore, any feasible direction algorithm
can give the solution of the problem. Jacobsen [9] applied the following feasible direction approach to the problem.

'''Algorithm 3'''

Step 1: Set <math>k = 0</math>. Choose <math> \epsilon > 0 </math> and select a point <math >x_k</math>.

Step 2: Solve the problem

<math>\max_{s\in S} \|x_k -s\|.</math>

Let <math>s_i</math> and <math>r_i</math> be a solution and the optimal objective function of the above problem, respectively, and let <math>U_i = \{s~ |~ r_i -\|x_k -s\| \leq \epsilon \}</math>.

Step 3: Based on <math>U_i</math>, determine the set of feasible descent directions from xk. If the set is empty, terminate the algorithm. Otherwise, select a feasible descent direction and calculate the step size in the direction. Denote the new solution <math>x_{k+1}</math> and set <math>k = k + 1</math>. Go to Step 2.


The optimization problem in Step 2 of Jacobsen's algorithm determines the minimum covering circle of the points in S with the center of <math>x_k</math>. It is proven that, in this infinite feasible direction method, <math>x_k</math> converges to the optimal solution <math>x^\ast</math>. The feasible descent direction in Step 3 is a cone and Jacobsen selects the bisector of the cone as the descent direction in the implementation. With this selection, Hearn and Vijay [8] proved that the feasible direction approach by Jacobsen is equivalent to the Chrystal-Peirce algorithm.

=References=

[1] R.K. Chakraborty and P.K. Chaudhuri, Note on Geometrical Solutions for Some Minimax Location Problems, Transportation Science, Vol. 15, 164-166 (1981)

[2] R. Chandrasekaran and A. Tamir, Optimization Problems with Algebraic Solutions: Quadratic Fractional Programs and Ratio Games, Mathematical Programming, Vol. 30, 326-339 (1984)

[3] G. Chrystal, On the Problem to Construct the Minimum Circle Enclosing n Given Points in the Plane, in Proceedings of the Edinburgh Mathematical Society, 3, 30-33 (1885)

[4] J. Elzinga and D.W. Hearn, The Minimum Covering Sphere Problem, Management Science, Vol. 19, 96-104 (1972)

[5] J. Elzinga and D.W. Hearn, Geometric Solutions for Some Minimax Location Problems, Transportation Science, Vol. 6, 379-394 (1972)

[6] J. Elzinga, D.W. Hearn and W.D. Randolph, Minimax Multifacility Location with Euclidean Distances, Transportation Science, Vol. 10, 321-336 (1976)

[7] Francis, R.L., L. F. McGinnis and J.A. White, Facility Layout and Location: An Analytical Approach, Second edition, Prentice-Hall, Inc., Englewood Cliffs, N.J. (1992)

[8] D.W. Hearn and J. Vijay, Efficient Algorithms for the (Weighted) Minimum Circle Problem, Operations Research, Vol. 30, No. 4, 777-795 (1982)

[9] S.K. Jacobsen, An Algorithm for the Minimax Weber Problem, European Journal of Operational Research, Vol. 6, 144-148 (1981)

[10] P. Kumar and E.A. Yildirim, A Core Set Result for the Weighted Euclidean One-Center Problem, Informs Journal on Computing, to appear (2009)

[11] C.L. Lawson, The Smallest Covering Cone or Sphere, SIAM Review, 415-417 (1965)

[12] N. Megiddo, Linear-Time Algorithms for Linear Programming in R3 and Related Problems, SIAM Journal on Computing, Vol. 12, 759-776 (1983)

[13] N. Megiddo, The Weighted Euclidean 1-Center Problem, Mathematics of Operations Research, Vol. 8, 498-504 (1983)

[14] N. Megiddo, Applying Parallel Algorithms in the Design of Serial Algorithms, Journal Assoc. Comput. Mach., Vol. 30, 852{865, (1983)

[15] N. Megiddo and E. Zemel, An O(n log n) Randomizing Algorithm for the Weighted Euclidean 1-Center Problem, Journal of Algorithms, VOl. 7, 358-368 (1986)

[16] M.I. Shamos and D. Hoey, Closest Point Problems, in Proceedings of 16 th Annual IEEE Symposium on Foundations of Computer Science, 151{162 (1975)

[17] S. Skyum, A Simple Algorithm for Computing the Smallest Enclosing Circle, Information Processing Letters, Vol. 37, 121-125 (1991)

[18] J.J. Sylvester, A Question in the Geometry of Situation, Quarterly Journal of Mathemaitcs, Vol. 1, p. 79 (1857)

[19] J.J. Sylvester, On Poncelet's Approximate Linear Valuation of Surd Forms, Philosophical Magazine, Vol. 20, 203-222 (1860)

[20] E.Welzl, Smallest Enclosing Disks (Balls and Ellipsoids), in H. Maurer (Ed.), New Results and New Trends in Computer Science, Lecture Notes in Computer Science, Vol. 555, Springer-Verlag, 359-37 (1991)

[21] S. Xu , R.M. Freund and J. Sun, Solution Methodologies for the Smallest Enclosing Circle Problem, Computational Optimization and Applications, Vol. 25, 283-292 (2003)

[22] G.L. Zhou , K.C. Tohemail and J. Sun, E±cient Algorithms for the Smallest Enclosing Ball Problem, Computational Optimization and Applications, Vol. 30, 147-160 (2005)


==See also==
* [[Centroid#Centroid_of_a_finite_set_of_points|Centroid of a finite set of points]]


==References==
{{reflist}}


==External links==
==External links==

Revision as of 07:13, 25 July 2009

The 1-center problem is a mathematical problem, in which we are given a set of points and we must find a circle covering all these points such that the radius of the circle is minimized. It is a special case of the bounding sphere problem and the minimax facility location problem of combinatorial optimization.

The problem can be solved in linear time via the prune and search strategy. [1]

See also

References

  1. ^ Lee, R. C. T. (2005). Introduction to the design and analysis of algorithms : a strategic approach. Singapore: McGraw-Hill p.9
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Smallest-circle_problem&oldid=304082601"