Largest Empty Sphere on:
[Wikipedia]
[Google]
[Amazon]
In
"The Largest Empty Circle Problem"
/ref>
In computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
, the largest empty sphere problem is the problem of finding a hypersphere
In mathematics, an -sphere or a hypersphere is a topological space that is homeomorphic to a ''standard'' -''sphere'', which is the set of points in -dimensional Euclidean space that are situated at a constant distance from a fixed point, cal ...
of largest radius in ''d''-dimensional space whose interior does not overlap with any given obstacles.
Two dimensions
The largest empty circle problem is the problem of finding acircle
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is const ...
of largest radius in the plane
In mathematics, a plane is a Euclidean (flat), two-dimensional surface that extends indefinitely. A plane is the two-dimensional analogue of a point (zero dimensions), a line (one dimension) and three-dimensional space. Planes can arise as ...
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
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
and enclosing none of them. The problem may be solved using Voronoi diagram
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...
s in optimal time .Megan Schuster"The Largest Empty Circle Problem"
/ref>
See also
*Bounding sphere
In mathematics, given a non-empty set of objects of finite extension in d-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an d-dimensional solid sphere containing all of thes ...
*Farthest-first traversal
In computational geometry, the farthest-first traversal of a compact metric space is a sequence of points in the space, where the first point is selected arbitrarily and each successive point is as far as possible from the set of previously-sel ...
*Largest empty rectangle
In computational geometry, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of finding a rectangle of maximal size to be placed among obstacles in the plane. There are a numb ...
References
{{reflist Geometric algorithms