Distance set

Last updated

In geometry, the distance set of a collection of points is the set of distances between distinct pairs of points. Thus, it can be seen as the generalization of a difference set, the set of distances (and their negations) in collections of numbers.

Several problems and results in geometry concern distance sets, usually based on the principle that a large collection of points must have a large distance set (for varying definitions of "large"):

Distance sets have also been used as a shape descriptor in computer vision. [10]

See also

Related Research Articles

<span class="mw-page-title-main">Equilateral triangle</span> Shape with three equal sides

An equilateral triangle is a triangle in which all three sides have the same length, and all three angles are equal. Because of these properties, the equilateral triangle is a regular polygon, occasionally known as the regular triangle. It is the special case of an isosceles triangle by modern definition, creating more special properties.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Lattice (group)</span> Periodic set of points

In geometry and group theory, a lattice in the real coordinate space is an infinite set of points in this space with the properties that coordinate-wise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be a subgroup of the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is a Delone set. More abstractly, a lattice can be described as a free abelian group of dimension which spans the vector space . For any basis of , the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as a regular tiling of a space by a primitive cell.

<span class="mw-page-title-main">Sylvester–Gallai theorem</span> Existence of a line through two points

The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. It is named after James Joseph Sylvester, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944.

<span class="mw-page-title-main">Hadwiger–Nelson problem</span> Mathematical problem

In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 5, 6 or 7. The correct value may depend on the choice of axioms for set theory.

In arithmetic geometry, the Bombieri–Lang conjecture is an unsolved problem conjectured by Enrico Bombieri and Serge Lang about the Zariski density of the set of rational points of an algebraic variety of general type.

Geometry is a branch of mathematics concerned with questions of shape, size, relative position of figures, and the properties of space. Geometry is one of the oldest mathematical sciences.

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

In geometry, the Beckman–Quarles theorem states that if a transformation of the Euclidean plane or a higher-dimensional Euclidean space preserves unit distances, then it preserves all Euclidean distances. Equivalently, every homomorphism from the unit distance graph of the plane to itself must be an isometry of the plane. The theorem is named after Frank S. Beckman and Donald A. Quarles Jr., who published this result in 1953; it was later rediscovered by other authors and re-proved in multiple ways. Analogous theorems for rational subsets of Euclidean spaces, or for non-Euclidean geometry, are also known.

The Erdős–Anning theorem states that, whenever an infinite number of points in the plane all have integer distances, the points lie on a straight line. The same result holds in higher dimensional Euclidean spaces. The theorem cannot be strengthened to give a finite bound on the number of points: there exist arbitrarily large finite sets of points that are not on a line and have integer distances.

<span class="mw-page-title-main">Equilateral dimension</span> Max number of equidistant points in a metric space

In mathematics, the equilateral dimension of a metric space is the maximum size of any subset of the space whose points are all at equal distances to each other. Equilateral dimension has also been called "metric dimension", but the term "metric dimension" also has many other inequivalent usages. The equilateral dimension of -dimensional Euclidean space is , achieved by the vertices of a regular simplex, and the equilateral dimension of a -dimensional vector space with the Chebyshev distance is , achieved by the vertices of a hypercube. However, the equilateral dimension of a space with the Manhattan distance is not known. Kusner's conjecture, named after Robert B. Kusner, states that it is exactly , achieved by the vertices of a cross polytope.

In geometry, the moment curve is an algebraic curve in d-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form

In geometric measure theory, Falconer's conjecture, named after Kenneth Falconer, is an unsolved problem concerning the sets of Euclidean distances between points in compact -dimensional spaces. Intuitively, it states that a set of points that is large in its Hausdorff dimension must determine a set of distances that is large in measure. More precisely, if is a compact set of points in -dimensional Euclidean space whose Hausdorff dimension is strictly greater than , then the conjecture states that the set of distances between pairs of points in must have nonzero Lebesgue measure.

In mathematics, the Erdős–Ulam problem asks whether the plane contains a dense set of points whose Euclidean distances are all rational numbers. It is named after Paul Erdős and Stanislaw Ulam.

<span class="mw-page-title-main">Isosceles set</span>

In discrete geometry, an isosceles set is a set of points with the property that every three of them form an isosceles triangle. More precisely, each three points should determine at most two distances; this also allows degenerate isosceles triangles formed by three equally-spaced points on a line.

<span class="mw-page-title-main">József Solymosi</span> Hungarian-Canadian mathematician

József Solymosi is a Hungarian-Canadian mathematician and a professor of mathematics at the University of British Columbia. His main research interests are arithmetic combinatorics, discrete geometry, graph theory, and combinatorial number theory.

Ilona Palásti (1924–1991) was a Hungarian mathematician who worked at the Alfréd Rényi Institute of Mathematics. She is known for her research in discrete geometry, geometric probability, and the theory of random graphs. With Alfréd Rényi and others, she was considered to be one of the members of the Hungarian School of Probability.

<span class="mw-page-title-main">Danzer set</span> Set of points touching all convex bodies of unit volume

In geometry, a Danzer set is a set of points that touches every convex body of unit volume. Ludwig Danzer asked whether it is possible for such a set to have bounded density. Several variations of this problem remain unsolved.

<span class="mw-page-title-main">Blichfeldt's theorem</span> High-area shapes can shift to hold many grid points

Blichfeldt's theorem is a mathematical theorem in the geometry of numbers, stating that whenever a bounded set in the Euclidean plane has area , it can be translated so that it includes at least points of the integer lattice. Equivalently, every bounded set of area contains a set of points whose coordinates all differ by integers.

References

  1. Arutyunyants, G.; Iosevich, A. (2004), "Falconer conjecture, spherical averages and discrete analogs", in Pach, János (ed.), Towards a Theory of Geometric Graphs, Contemp. Math., vol. 342, Amer. Math. Soc., Providence, RI, pp. 15–24, doi: 10.1090/conm/342/06127 , MR   2065249
  2. Klee, Victor; Wagon, Stan (1991), "Problem 10 Does the plane contain a dense rational set?", Old and New Unsolved Problems in Plane Geometry and Number Theory, Dolciani mathematical expositions, vol. 11, Cambridge University Press, pp. 132–135, ISBN   978-0-88385-315-3 .
  3. Magyar, Ákos (2008), "On distance sets of large sets of integer points", Israel Journal of Mathematics , 164: 251–263, doi: 10.1007/s11856-008-0028-z , MR   2391148, S2CID   17629304
  4. Anning, Norman H.; Erdős, Paul (1945), "Integral distances", Bulletin of the American Mathematical Society , 51 (8): 598–600, doi: 10.1090/S0002-9904-1945-08407-9 .
  5. Guth, Larry; Katz, Nets Hawk (2015), "On the Erdős distinct distances problem in the plane", Annals of Mathematics , 181 (1): 155–190, arXiv: 1011.4105 , doi:10.4007/annals.2015.181.1.2, MR   3272924, S2CID   43051852
  6. Bekir, Ahmad; Golomb, Solomon W. (2007), "There are no further counterexamples to S. Piccard's theorem", IEEE Transactions on Information Theory , 53 (8): 2864–2867, doi:10.1109/TIT.2007.899468, MR   2400501, S2CID   16689687
  7. Koolen, Jack; Laurent, Monique; Schrijver, Alexander (2000), "Equilateral dimension of the rectilinear space", Designs, Codes and Cryptography, 21 (1): 149–164, doi:10.1023/A:1008391712305, MR   1801196, S2CID   9391925
  8. Szöllösi, Ferenc (2018), "The Two-Distance Sets in Dimension Four", in Akiyama, Jin; Marcelo, Reginaldo M.; Ruiz, Mari-Jo P.; Uno, Yushi (eds.), Discrete and Computational Geometry, Graphs, and Games - 21st Japanese Conference, JCDCGGG 2018, Quezon City, Philippines, September 1-3, 2018, Revised Selected Papers, Lecture Notes in Computer Science, vol. 13034, Springer, pp. 18–27, arXiv: 1806.07861 , doi:10.1007/978-3-030-90048-9_2, MR   4390269
  9. Blokhuis, A. (1983), "Chapter 7: Isosceles point sets", Few-Distance Sets (Ph.D. thesis), Eindhoven University of Technology, pp. 46–49, doi:10.6100/IR53747, Zbl   0516.05017
  10. Grigorescu, C.; Petkov, N. (October 2003), "Distance sets for shape filters and shape recognition" (PDF), IEEE Transactions on Image Processing, 12 (10): 1274–1286, doi:10.1109/tip.2003.816010, hdl: 11370/dd4f402f-91b0-47ae-94ec-29428a2d8fb9 , PMID   18237892