Largest empty circle on:
[Wikipedia]
[Google]
[Amazon]
In computational geometry, the largest empty sphere problem is the problem of finding a
"The Largest Empty Circle Problem"
/ref>
In computational geometry, 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, call ...
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 con ...
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 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 ...
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 the ...
*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-selec ...
*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