|
Covering Radius
In the mathematical theory of metric spaces, ε-nets, ε-packings, ε-coverings, uniformly discrete sets, relatively dense sets, and Delone sets (named after Boris Delone) are several closely related definitions of well-spaced sets of points, and the packing radius and covering radius of these sets measure how well-spaced they are. These sets have applications in coding theory, approximation algorithms, and the theory of quasicrystals. Definitions If (''M'',''d'') is a metric space, and ''X'' is a subset of ''M'', then the packing radius of ''X'' is half of the infimum of distances between distinct members of ''X''. If the packing radius is ''r'', then open balls of radius ''r'' centered at the points of ''X'' will all be disjoint from each other, and each open ball centered at one of the points of ''X'' with radius 2''r'' will be disjoint from the rest of ''X''. The covering radius of ''X'' is the infimum of the numbers ''r'' such that every point of ''M'' is within distanc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Metric Epsilon-net
Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathematics, metric may refer to one of two related, but distinct concepts: * A function which measures distance between two points in a metric space * A metric tensor, in differential geometry, which allows defining lengths of curves, angles, and distances in a manifold Natural sciences * Metric tensor (general relativity), the fundamental object of study in general relativity, similar to the gravitational field in Newtonian physics * Senses related to measurement: ** Metric system, an internationally adopted decimal system of measurement ** Metric units, units related to a metric system ** International System of Units, or ''Système International'' (SI), the most widely used metric system * METRIC, a model that uses Landsat satellite data to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Doubling Space
In mathematics, a metric space with metric is said to be doubling if there is some doubling constant such that for any and , it is possible to cover the ball with the union of at most balls of radius . The base-2 logarithm of is called the doubling dimension of . Euclidean spaces \mathbb^d equipped with the usual Euclidean metric are examples of doubling spaces where the doubling constant depends on the dimension . For example, in one dimension, ; and in two dimensions, . In general, Euclidean space \mathbb^d has doubling dimension \Theta(d). Assouad's embedding theorem An important question in metric space geometry is to characterize those metric spaces that can be embedded in some Euclidean space by a bi-Lipschitz function. This means that one can essentially think of the metric space as a subset of Euclidean space. Not all metric spaces may be embedded in Euclidean space. Doubling metric spaces, on the other hand, would seem like they have more of a chance, since ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Yves Meyer
Yves F. Meyer (; born 19 July 1939) is a French mathematician. He is among the progenitors of wavelet theory, having proposed the Meyer wavelet. Meyer was awarded the Abel Prize in 2017. Biography Born in Paris to a Jewish family, Yves Meyer studied at the Lycée Carnot in Tunis; he won the French General Student Competition (Concours Général) in Mathematics, and was placed first in the entrance examination for the École Normale Supérieure in 1957. He obtained his Ph.D. in 1966, under the supervision of Jean-Pierre Kahane. The Mexican historian Jean Meyer is his cousin. Yves Meyer taught at the Prytanée national militaire during his military service (1960–1963), then was a teaching assistant at the Université de Strasbourg (1963–1966), a professor at Université Paris-Sud (1966–1980), a professor at École Polytechnique (1980–1986), a professor at Université Paris-Dauphine (1985–1995), a senior researcher at the Centre national de la recherche scientifique (CN ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minkowski Difference
In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set : A + B = \. Analogously, the Minkowski difference (or geometric difference) is defined using the complement operation as : A - B = \left(A^c + (-B)\right)^c In general A - B \ne A + (-B). For instance, in a one-dimensional case A = 2, 2/math> and B = 1, 1/math> the Minkowski difference A - B = 1, 1/math>, whereas A + (-B) = A + B = 3, 3 In a two-dimensional case, Minkowski difference is closely related to erosion (morphology) in image processing. The concept is named for Hermann Minkowski. Example For example, if we have two sets ''A'' and ''B'', each consisting of three position vectors (informally, three points), representing the vertices of two triangles in \mathbb^2, with coordinates :A = \ and :B = \ then their Minkowski sum is :A + B = \ which comp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Meyer Set
In mathematics, a Meyer set or almost lattice is a set relatively dense ''X'' of points in the Euclidean plane or a higher-dimensional Euclidean space such that its Minkowski difference with itself is uniformly discrete. Meyer sets have several equivalent characterizations; they are named after Yves Meyer, who introduced and studied them in the context of diophantine approximation. Nowadays Meyer sets are best known as mathematical model for quasicrystals. However, Meyer's work precedes the discovery of quasicrystals by more than a decade and was entirely motivated by number theoretic questions.. Definition and characterizations A subset ''X'' of a metric space is relatively dense if there exists a number ''r'' such that all points of ''X'' are within distance ''r'' of ''X'', and it is uniformly discrete if there exists a number ''ε'' such that no two points of ''X'' are within distance ''ε'' of each other. A set that is both relatively dense and uniformly discr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nearest Neighbor Search
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 (or most similar) 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. Most commonly ''M'' is a metric space and dissimilarity is expressed as a distance metric, which is symmetric and satisfies the triangle inequality. Even more common, ''M'' is taken ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Geometric Spanner
A geometric spanner or a -spanner graph or a -spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a -path between any pair of vertices for a fixed parameter . A -path is defined as a path through the graph with weight at most times the spatial distance between its endpoints. The parameter is called the stretch factor or dilation factor of the spanner. In computational geometry, the concept was first discussed by L.P. Chew in 1986, although the term "spanner" was not used in the original paper. The notion of graph spanners has been known in graph theory: -spanners are spanning subgraphs of graphs with similar dilation property, where distances between graph vertices are defined in graph-theoretical terms. Therefore geometric spanners are graph spanners of complete graphs embedded in the plane with edge weights equal to the distances between the embedded vertices in the corresponding metric. Spanners may be used in co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Well-separated Pair Decomposition
In computational geometry, a well-separated pair decomposition (WSPD) of a set of points S \subset \mathbb^d, is a sequence of pairs of sets (A_i, B_i), such that each pair is well-separated, and for each two distinct points p, q \in S, there exists precisely one pair which separates the two. The graph induced by a well-separated pair decomposition can serve as a k-spanner of the complete Euclidean graph, and is useful in approximating solutions to several problems pertaining to this. Definition Let A, B be two disjoint sets of points in \mathbb^d, R(X) denote the axis-aligned minimum bounding box for the points in X, and s > 0 denote the separation factor. We consider A and B to be well-separated, if for each of R(A) and R(B) there exists a d-ball of radius \rho containing it, such that the two spheres have a minimum distance of at least s \rho. We consider a sequence of well-separated pairs of subsets of S, (A_1, B_1), (A_2, B_2), \ldots, (A_m,B_m) to be a well-separated ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-center
In graph theory, the metric -center problem is a combinatorial optimization problem studied in theoretical computer science. Given cities with specified distances, one wants to build warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of vertices for which the largest distance of any point to its closest vertex in the -set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality. Formal definition Let (X,d) be a metric space where X is a set and d is a metric A set \mathbf\subseteq\mathcal, is provided together with a parameter k. The goal is to find a subset \mathcal\subseteq \mathbf with , \mathcal, =k such that the maximum distance of a point in \mathbf to the closest point in \mathcal is minimized. The problem can be formally defined as follows: For a metric space (\mathcal,d), * Input: a set \mathbf\subseteq\mathcal, and a param ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Euclidean Space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any positive integer dimension (mathematics), dimension, including the three-dimensional space and the ''Euclidean plane'' (dimension two). The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics. Ancient History of geometry#Greek geometry, Greek geometers introduced Euclidean space for modeling the physical space. Their work was collected by the Greek mathematics, ancient Greek mathematician Euclid in his ''Elements'', with the great innovation of ''mathematical proof, proving'' all properties of the space as theorems, by starting from a few fundamental properties, called ''postulates'', which either were considered as eviden ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hamming Metric
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to change one string into the other, or the minimum number of ''errors'' that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is named after the American mathematician Richard Hamming. A major application is in coding theory, more specifically to block codes, in which the equal-length strings are vectors over a finite field. Definition The Hamming distance between two equal-length strings of symbols is the number of positions at which the corresponding symbols are different. Examples The symbols may be letters, bits, or decimal digits, among other possibilities. For example, the Hamming distance bet ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Coordinate Vector
In linear algebra, a coordinate vector is a representation of a vector as an ordered list of numbers (a tuple) that describes the vector in terms of a particular ordered basis. An easy example may be a position such as (5, 2, 1) in a 3-dimensional Cartesian coordinate system with the basis as the axes of this system. Coordinates are always specified relative to an ordered basis. Bases and their associated coordinate representations let one realize vector spaces and linear transformations concretely as column vectors, row vectors, and matrices; hence, they are useful in calculations. The idea of a coordinate vector can also be used for infinite-dimensional vector spaces, as addressed below. Definition Let ''V'' be a vector space of dimension ''n'' over a field ''F'' and let : B = \ be an ordered basis for ''V''. Then for every v \in V there is a unique linear combination of the basis vectors that equals '' v '': : v = \alpha _1 b_1 + \alpha _2 b_2 + \cdots + \alpha _n b_n . ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
