Placing a point to minimise distance from the fart

Question

I have a question,

Given a set of points , how do you place a point with the constraint that the distance to the farthest point is as small as possible?.

This is in reference to this problem. I do not know how to proceed. Some pointers anyone?

Thanks

Answer 1

Check out this page. It describes several methods to do this. http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

_{In case the link above ever dies, here's the relevant part that describes the most straight-forward method:}

---

An O(n2)-time Algorithm

1. Draw a circle at center, c, such that points of given set lie within the circle. Clearly, this circle can be made smaller (or else we have the solution).
2. Make a circle smaller by finding the point A farthest from the center of circler, and drawing a new circle with the same center and passing through the point A. These two steps produce a smaller enclosing circle. The reason that the new circle is smaller is that this new circle still contains all the points of given set, except now it passes through farthest point, x, rather than enclosing it.
3. If the circle passes through 2 or more points, proceed to step 4. Otherwise, make the circle smaller by moving the center towards point A, until the circle makes contact with another point B from the set.

4. At this stage, we a circle, C, that passes through two or more points of a given set. If the circle contains an interval (point-free interval) of arc greater than half the circle's circumference on which no points lie, the circle can be made smaller. Let D and E be the points at the ends of this point-free interval. While keeping D and E on the circle's boundary, reduce the diameter of the circle until we have either case (a) or case (b).

   • Case (a) The diameter is the distance DE.
     • We are done!
   • Case (b) The circle C touches another point from the set, F.
     • Check whether there exits point-free arc intervals of length more than half the circumference of C.
     • IF no such point-free arc intervals exit THEN We are done!
   • Else
     • Goto step 4.
     • In this case, three points must lie on an arc less than half the circumference in length. We repeat step 4 on the outer two of the three points on the arc.

---

Another page here, with a sample applet: http://www.sunshine2k.de/stuff/Java/Welzl/Welzl.html

Answer 2

You need to use the Voronoi diagram, possibibly the Farthest-Point Voronoi diagram, where the plane is divided into regions, where points in the same region have the same fartherst point

Update

You need to build a Farthest-Point voronoi diagram first, which is O(nlogn) time, and find the center of the smallest circle among all the vertices(if the circle is defined by three points) and all the edges(if the circle is defined by two points). The total time complexity of this approach is O(nlogn)

I just saw the Smallest circle problem wiki page, seems like there is a O(n) time algorithm. You can check it out if you care about the speed, otherwise never mind.