Smallest Circle Problem

number of points

100

The smallest circle problem for a set of two-dimensional points seeks to find the smallest-radius circle that contains all the points. This Demonstration uses the Matoušek, Sharir and Welzl (MSW) algorithm [1] that computes the circle for

points in expected

O(n)

time. Move the locators to interact with the solution and use the slider to change the number of points.

The built-in Wolfram Language function BoundingRegion uses a similar method.

Details

The smallest circle problem is also known as the minimum covering circle problem, bounding circle problem or smallest enclosing circle problem. For

points, a naive solution runs in

)

time, but this randomized algorithm runs in expected linear time, using the MSW algorithm [1]. This recursive algorithm builds and corrects the bounding circle. It returns the minimum circle

D={(x,y),r}

, with circle center

(x,y)

and the radius

. See the initialization code for implementations of the functions msw, trivialMinCircle and nonbase.

msw algorithm: input: finite sets

and

of points in the plane,

R=3

output: minimal disk enclosing

P⋃R

is empty return trivialMinCircle(

) choose

p∈P

(randomly and uniformly)

P:=P-{p}

D:=msw(P,R)

p∈D

q=nonbase(R⋃{p})

return

msw(P⋃{q},R⋃{p}-{q})

References

[1] J. Matsuoka, M. Sharir and E. Welzl, "A Subexponential Bound for Linear Programming," Algorithmica, 16(4–5), 1996 pp. 498–516. doi:10.1007/BF01940877.

External Links

BoundingRegion (Wolfram Documentation Center)

Circumcircle (Wolfram MathWorld)

Diameter (Wolfram MathWorld)

Disk Point Picking (Wolfram MathWorld)

Minimal Enclosing Circle (Wolfram MathWorld)

The Bomb Problem

Minimal Enclosing Circle

Enclosing Circle (Wolfram MathWorld)

The Facilities Location Problem

Permanent Citation

Mohammad Sultan, Aaron T. Becker

"Smallest Circle Problem" from the Wolfram Demonstrations Project http://demonstrations.wolfram.com/SmallestCircleProblem/
Published: December 9, 2019