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.
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.
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]
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 constant. The distance between any point of the circle and the centre is called the radius. Usually, the radius is required to be a positive number. A circle with is a degenerate case. This article is about circles in Euclidean geometry, and, in particular, the Euclidean plane, except where otherwise noted.
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for the diameter of a sphere.
A sphere is a geometrical object that is a three-dimensional analogue to a two-dimensional circle. A sphere is the set of points that are all at the same distance r from a given point in three-dimensional space. That given point is the centre of the sphere, and r is the sphere's radius. The earliest known mentions of spheres appear in the work of the ancient Greek mathematicians.
Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.
In mathematics, the open unit disk around P, is the set of points whose distance from P is less than 1:
The Method of Mechanical Theorems, also referred to as The Method, is one of the major surviving works of the ancient Greek polymath Archimedes. The Method takes the form of a letter from Archimedes to Eratosthenes, the chief librarian at the Library of Alexandria, and contains the first attested explicit use of indivisibles. The work was originally thought to be lost, but in 1906 was rediscovered in the celebrated Archimedes Palimpsest. The palimpsest includes Archimedes' account of the "mechanical method", so called because it relies on the center of weights of figures (centroid) and the law of the lever, which were demonstrated by Archimedes in On the Equilibrium of Planes.
A circle of a sphere is a circle that lies on a sphere. Such a circle can be formed as the intersection of a sphere and a plane, or of two spheres. Circles of a sphere are the spherical geometry analogs of generalised circles in Euclidean space. A circle on a sphere whose plane passes through the center of the sphere is called a great circle, analogous to a Euclidean straight line; otherwise it is a small circle, analogous to a Euclidean circle. Circles of a sphere have radius less than or equal to the sphere radius, with equality when the circle is a great circle.
In geometry, a sphere packing is an arrangement of non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three-dimensional Euclidean space. However, sphere packing problems can be generalised to consider unequal spheres, spaces of other dimensions or to non-Euclidean spaces such as hyperbolic space.
The great-circle distance, orthodromic distance, or spherical distance is the distance along a great circle.
In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another.
A cylinder has traditionally been a three-dimensional solid, one of the most basic of curvilinear geometric shapes. In elementary geometry, it is considered a prism with a circle as its base.
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.
In classical geometry, a radius of a circle or sphere is any of the line segments from its center to its perimeter, and in more modern usage, it is also their length. The name comes from the latin radius, meaning ray but also the spoke of a chariot wheel. The plural of radius can be either radii or the conventional English plural radiuses. The typical abbreviation and mathematical variable name for radius is R or r. By extension, the diameter D is defined as twice the radius:
In Euclidean plane geometry, Apollonius's problem is to construct circles that are tangent to three given circles in a plane (Figure 1). Apollonius of Perga posed and solved this famous problem in his work Ἐπαφαί ; this work has been lost, but a 4th-century AD report of his results by Pappus of Alexandria has survived. Three given circles generically have eight different circles that are tangent to them (Figure 2), a pair of solutions for each way to divide the three given circles in two subsets.
Proximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects.
The smallest-circle problem is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857.
Lie sphere geometry is a geometrical theory of planar or spatial geometry in which the fundamental concept is the circle or sphere. It was introduced by Sophus Lie in the nineteenth century. The main idea which leads to Lie sphere geometry is that lines should be regarded as circles of infinite radius and that points in the plane should be regarded as circles of zero radius.
The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph:
In geometry, Cavalieri's principle, a modern implementation of the method of indivisibles, named after Bonaventura Cavalieri, is as follows:
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 number of variants of the problem, depending on the particularities of this generic formulation, in particular, depending on the measure of the "size", domain, and the orientation of the rectangle.
