Geometrical solutions for some minimax location problems

Put  some dots randomly on a piece of paper and draw the smallest possible circle around them. Recently I have been struggling with this little problem. Finally I understood that my solution was wrong and the follwoing algorithm was correct:

1. Choose any two points, Pi and Pj

2. Construct the circle whose center is at the midpoint of the line connecting Pi and Pj and which passes through Pi and Pj.  If this circle contains all points, then the center of the circle is the optimal X. Otherwise, choose a point Pk outside the circle.

3. If the triangle determined by Pi, Pj and Pk is a right triangle or an obtuse triangle, rename the two points opposite the right angle or the obtuse angle as Pi and Pj  and go to step 2.  Otherwise, the three points determine an acute triangle. Construct the circle passing through the three points. (The center is the intersection of the perpendicular bisectors of two sides of the triangle.) If the circle contains all the points, stop,else, go to 4.

4. Choose some point Pl not in the circle, and let Q be the point among {Pi, Pj, Pk} that is greatest distance from Pl. Extend the diameter (from the circle center) through the point Q into a line that divides the plane into two half planes. Let the point R be the point among {Pi, Pj, Pk} that is in the half plane opposite Pl. With the points Q, R, and Pl, go to step 3.

D. Jack Elzinga, Donald W. Hearn, “Geometrical Solutions for some minimax location problems,”  Transportation Science, 6, (1972), pp 379 – 394.[url]

Leave a Reply