📑 Table of Contents▼
The dashed circle is the outline of the largest empty sphere in the close-packing of spheres. See also Interstitial defect.
Finding the largest empty circle using the Voronoi diagram (two solutions).

In computational geometry, the largest empty sphere problem is the problem of finding a hypersphere of largest radius in d-dimensional space whose interior does not overlap with any given obstacles.

Two dimensions

edit

The largest empty circle problem is the problem of finding a circle of largest radius in the plane whose interior does not overlap with any given obstacles.

A common special case is as follows. Given n points in the plane, find a largest circle centered within their convex hull and enclosing none of them. The problem may be solved using Voronoi diagrams in optimal time .[1][2]

See also

edit

References

edit
  1. ^ G. T. Toussaint, "Computing largest empty circles with location constraints," International Journal of Computer and Information Sciences, vol. 12, No. 5, October, 1983, pp. 347-358.
  2. ^ Megan Schuster, "The Largest Empty Circle Problem"

📚 Artikel Terkait di Wikipedia

Largest empty rectangle

In computational geometry, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of

Sphere

A sphere (from Ancient Greek σφαῖρα (sphaîra) 'ball') is a surface analogous to the circle, a curve. In solid geometry, a sphere is the set of points that

Ulam's packing conjecture

of space to remain empty in its optimal packing structure. This conjecture is therefore related to the Kepler conjecture about sphere packing. Since the

List of combinatorial computational geometry topics

bounding sphere (Smallest enclosing sphere) 2-D case: Smallest bounding circle Largest empty rectangle (Maximum empty rectangle) Largest empty sphere 2-D case:

Optimal facility location

Euclidean metric, it is known as the largest empty sphere problem. The planar single-facility case (largest empty circle problem) may be solved in optimal

Bounding sphere

non-empty set of objects of finite extension in d {\displaystyle d} -dimensional space, for example a set of points, a bounding sphere, enclosing sphere or

Sinosphere

Quốc ngữ. The Sinosphere, also known as the Chinese cultural sphere, East Asian cultural sphere, or the Sinic world, encompasses multiple countries in East

U2:UV Achtung Baby Live at Sphere

U2:UV Achtung Baby Live at Sphere was a concert residency by the Irish rock band U2 that took place at Sphere in Paradise, Nevada, in the Las Vegas Valley