Smallest Circle Enclosing Points

From CGAFaq

Jump to: navigation, search

The smallest circle enclosing a collection of points is often called the minimum spanning circle. It can be computed in O(n log n) time for n points. The center lies on the furthest-point Voronoi diagram. Computing the diagram constrains the search for the center. Constructing the diagram can be accomplished by a 3D convex hull algorithm; for that connection, see, e.g., [O'Rourke (C), p.195ff]. For direct algorithms, see:

  • S. Skyum, A simple algorithm for computing the smallest enclosing circle. Inform. Process. Lett. 37 (1991) 121–125.
  • J. Rokne, An Easy Bounding Circle [Gems II] pp.14--16.
Retrieved from "http://www.cgafaq.info/wiki/Smallest_Circle_Enclosing_Points"
Personal tools