Smallest Circle Problem

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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 time. Move the locators to interact with the solution and use the slider to change the number of points.

[more]

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

[less]

Contributed by: Mohammad Sultan and Aaron T. Becker (December 2019)
Open content licensed under CC BY-NC-SA


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 , with circle center 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, output: minimal disk enclosing if is empty return trivialMinCircle() choose (randomly and uniformly) if : return

Reference

[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.


Snapshots



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send