Proximity problems

Last updated May 03, 2019

Proximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects.

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 geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with history stretching back to antiquity.

Distance is a numerical measurement of how far apart objects are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria. In most cases, "distance from A to B" is interchangeable with "distance from B to A". In mathematics, a distance function or metric is a generalization of the concept of physical distance. A metric is a function that behaves according to a specific set of rules, and is a way of describing what it means for elements of some space to be "close to" or "far away from" each other.

Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values. Formally, the nearest-neighbor (NN) search problem is defined as follows: given a set S of points in a space M and a query point q ∈ M, find the closest point in S to q. Donald Knuth in vol. 3 of The Art of Computer Programming (1973) called it the post-office problem, referring to an application of assigning to a residence the nearest post office. A direct generalization of this problem is a k-NN search, where we need to find the k closest points.

A common trait for many of these problems is the possibility to establish the Θ(n log n) lower bound on their computational complexity by reduction from the element uniqueness problem basing on an observation that if there is an efficient algorithm to compute some kind of minimal distance for a set of objects, it is trivial to check whether this distance equals to 0.

Big O notation notation to describe the limiting behavior of a function

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.

Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

Atomic problems

While these problems pose no computational complexity challenge, some of them are notable because of their ubiquity in computer applications of geometry.

Distance between a pair of line segments. It cannot be expressed by a single formula, unlike, e.g., the distance from a point to a line. Its calculation requires careful enumeration of possible configurations, especially in 3D and higher dimensions.^[2]
Bounding box, the minimal axis-aligned hyperrectangle that contains all geometric data

In geometry, a line segment is a part of a line that is bounded by two distinct end points, and contains every point on the line between its endpoints. A closed line segment includes both endpoints, while an open line segment excludes both endpoints; a half-open line segment includes exactly one of the endpoints.

The distancefrom a point to a line is the shortest distance from a fixed point to any point on a fixed infinite line in Euclidean geometry. It is the length of the line segment which joins the point to the line and is perpendicular to the line. The formula for calculating it can be derived and expressed in several ways.

In geometry, an n-orthotope is the generalization of a rectangle for higher dimensions, formally defined as the Cartesian product of intervals.

Problems on points

Closest pair of points: Given N points, find two with the smallest distance between them
Closest point query / nearest neighbor query: Given N points, find one with the smallest distance to a given query point
All nearest neighbors problem (construction of the nearest-neighbor graph): Given N points, find a closest one for each of them
Diameter of a point set: Given N points, find two with the largest distance between them
Width of a point set: Given N points, find two (hyper)planes with the smallest distance between them and with all points between them
Minimum spanning tree for a set of points
- Euclidean minimum spanning tree
Delaunay triangulation
Voronoi diagram
Smallest enclosing sphere: Given N points, find a smallest sphere (circle) enclosing them all
Largest empty circle: Given N points in the plane, find a largest circle centered within their convex hull and enclosing none of them
Smallest enclosing rectangle: unlike the bounding box problem mentioned above, the rectangle may be of any orientation
Largest empty rectangle
geometric spanner, a weighted graph over a set of points as its vertices which for every pair of vertices has a path between them of weight at most 'k' times the spatial distance between these points for a fixed 'k'.

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane, where the weight of the edge between each pair of points is the Euclidean distance between those two points. In simpler terms, an EMST connects a set of dots using lines such that the total length of all the lines is minimized and any dot can be reached from any other by following the lines.

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

Other

Distance of closest approach of ellipses and ellipsoids

The distance of closest approach of two objects is the distance between their centers when they are externally tangent. The objects may be geometric shapes or physical particles with well defined boundaries. The distance of closest approach is sometimes referred to as the contact distance.

Related Research Articles

In mathematics, a Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. That set of points is specified beforehand, and for each seed there is a corresponding region consisting of all points closer to that seed than to any other. These regions are called Voronoi cells. The Voronoi diagram of a set of points is dual to its Delaunay triangulation.

In mathematics, given a non-empty set of objects of finite extension in $-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an -dimensional solid sphere containing all of these objects.$

In geometry a simple polygon is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pair-wise to form a closed path. If the sides intersect then the polygon is not simple. The qualifier "simple" is frequently omitted, with the above definition then being understood to define a polygon in general.

<i>k</i>-d tree multidimensional search tree for points in k dimensional space

In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key. k-d trees are a special case of binary space partitioning trees.

The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane was among the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms.

A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner.

In computational geometry, a planar straight-line graph, in short PSLG, is a term used for an embedding of a planar graph in the plane such that its edges are mapped into straight line segments. Fáry's theorem (1948) states that every planar graph has this kind of embedding.

The nearest neighbor graph (NNG) for a set of n objects P in a metric space is a directed graph with P being its vertex set and with a directed edge from p to q whenever q is a nearest neighbor of p.

In geometry, the minimum or smallest bounding or enclosing box for a point set (S) in N dimensions is the box with the smallest measure within which all the points lie. When other kinds of measure are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box".

In computational geometry, the smallest enclosing box problem is that of finding the oriented minimum bounding box enclosing a set of points. It is a type of bounding volume. "Smallest" may refer to volume, area, perimeter, etc. of the box.

The smallest-circle problem or minimum covering 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.

In computational geometry, the fixed-radius near neighbor problem is a variant of the nearest neighbor search problem. In the fixed-radius near neighbor problem, one is given as input a set of points in d-dimensional Euclidean space and a fixed distance Δ. One must design a data structure that, given a query point q, efficiently reports the points of the data structure that are within distance Δ of q. The problem has long been studied; Bentley (1975) cites a 1966 paper by Levinthal that uses this technique as part of a system for visualizing molecular structures, and it has many other applications.

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 the study of algorithms, an LP-type problem is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.

A geometric separator is a line that partitions a collection of geometric shapes into two subsets, such that proportion of shapes in each subset is bounded, and the number of shapes that do not belong to any subset is small.

In geometric graph theory, a penny graph is a contact graph of unit circles. That is, it is an undirected graph whose vertices can be represented by unit circles, with no two of these circles crossing each other, and with two adjacent vertices if and only if they are represented by tangent circles. More simply, they are the graphs formed by arranging pennies in a non-overlapping way on a flat surface, making a vertex for each penny, and making an edge for each two pennies that touch.

References

Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. ISBN 0-387-96131-3. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6. The proximity problems are covered in chapters 6 and 7.

↑ J. R. Sack and J. Urrutia (eds.) (2000). Handbook of Computational Geometry. North Holland. ISBN 0-444-82537-1.CS1 maint: Extra text: authors list (link)
↑ V. J. Lumelsky (1985). "On fast computation of distance between line segments". Inf. Process. Lett. 21 (2): 55–61. doi:10.1016/0020-0190(85)90032-8.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] J. R. Sack and J. Urrutia (eds.) (2000). Handbook of Computational Geometry. North Holland. ISBN 0-444-82537-1.CS1 maint: Extra text: authors list (link)

[2] V. J. Lumelsky (1985). "On fast computation of distance between line segments". Inf. Process. Lett. 21 (2): 55–61. doi:10.1016/0020-0190(85)90032-8.