Largest empty sphere
Encyclopedia
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.
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 diagram
s in optimal time
.
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 are also considered to be part of computational...
, the largest empty sphere problem is the problem of finding a hypersphere
Hypersphere
In mathematics, an n-sphere is a generalization of the surface of an ordinary sphere to arbitrary dimension. For any natural number n, an n-sphere of radius r is defined as the set of points in -dimensional Euclidean space which are at distance r from a central point, where the radius r may be any...
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 a circleCircle
A circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....
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
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
and enclosing none of them. The problem may be solved using Voronoi diagram
Voronoi diagram
In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
s in optimal time
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
.