CODEWITHSUNDEEP
algorithmcomputational-geometry
Leonid
Leonid

Reputation: 23490

Smallest circle which covers given points on 2D plane

Problem: What is the smallest possible diameter of a circle which covers given N points on a 2D plane?

What is the most efficient algorithm to solve this problem and how does it work?

Upvotes: 8

Views: 11763

Answers (3)

agentp
agentp

Reputation: 6999

the furthest point voronoi diagram approach

http://www.dma.fi.upm.es/mabellanas/tfcs/fvd/algorithm.html

turns out to work really well for the 2 d problem. It is non-iterative and (pretty sure) guaranteed exact. I suspect it doesn't extend so well to higher dimensions, which is why there is little attention to it in the literature.

If there is interest i'll describe it here - the above link is a bit hard to follow I think.

edit another link: http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6704

Upvotes: 1

Hbf
Hbf

Reputation: 3114

There are several algorithms and implementations out there for the Smallest enclosing balls problem.

  • For 2D and 3D, Gärtner's implementation is probably the fastest.

  • For higher dimensions (up to 10,000, say), take a look at https://github.com/hbf/miniball, which is the implementation of an algorithm by Gärtner, Kutz, and Fischer (note: I am one of the co-authors).

  • For very, very high dimensions, core-set (approximation) algorithms will be faster.

Note: If you are looking for an algorithm to compute the smallest enclosing sphere of spheres, you will find a C++ implementation in the Computational Geometry Algorithms Library (CGAL). (You do not need to use all of CGAL; simply extract the required header and source files.)

Upvotes: 6

Benjamin
Benjamin

Reputation: 11860

This is the smallest circle problem. See the references for the links to the suggested algorithms.

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)

is the reference to the "fastest" algorithm.

Upvotes: 8

Related Questions