2006 DictionaryofDistances

Jump to: navigation, search

Subject Headings: Distance Function.


Cited By


Book Overview

Key features:


The concept of distance is basic to human experience. In everyday life it usually means some degree of closeness of two physical objects or ideas, i.e., length, time interval, gap, rank difference, coolness or remoteness, while the term metric is often used as a standard for a measurement.

But here we consider, except for the last two chapters, the mathematical meaning of those terms, which is an abstraction of measurement.

The mathematical notions of distance metric (i.e., a function d (x, y) from X × X to the set of real numbers satisfying to d (x, y) = 0 with equality only for x = y, d (x, y) = d (y, x), and d (x, y) = d (x, z) +d (z, y)) and of metric space (X, d) were originated a century ago by M. Fréchet (1906) and F. Hausdor (1914) as a special case of an infinite topological space. The triangle inequality above appears already in Euclid. The infinite metric spaces are usually seen as a generalization of the metric|x - y|on the real numbers. Their main classes are the measurable spaces (add measure) and Banach spaces (add norm and completeness).

However, starting from K. Menger (who, in 1928, introduced metric spaces in Geometry) and L.M. Blumenthal (1953), an explosion of interest in both finite and infinite metric spaces occurred. Another trend is that many mathematical theories, in the process of their generalization, settled on the level of metric space. It is an ongoing process, for example, for Riemannian geometry, Real Analysis, Approximation Theory.

Distance metrics and distances have now become an essential tool in many areas of Mathematics and its applications including Geometry, Probability, Statistics, Coding / Graph Theory, Clustering, Data Analysis, Pattern Recognition, Networks, Engineering, Computer Graphics / Vision, Astronomy, Cosmology, Molecular Biology, and many other areas of science. Devising the most suitable distance metrics and similarities, to quantify the proximity between objects, has become a standard task for many researchers. Especially intense ongoing search for such distances occurs, for example, in Computational Biology, Image Analysis, Speech Recognition, and Information Retrieval.

Often the same distance metric appears independently in several different areas; for example, the edit distance between words, the evolutionary distance in Biology, the Levenstein distance in Coding Theory, and the Hamming + Gap or shuffle-Hamming distance.

This body of knowledge has become too big and disparate to operate in. The numbers of worldwide web entries offered by Google on the topics “distance,” “metric space” and “distance metric” approach 300 million (i.e., about 2% of all), 6.5 million and 5.5 million, respectively, not to mention all the printed information outside the Web, or the vast “invisible Web” of searchable databases. However, this vast information on distances is too scattered: the works evaluating distance from some list usually treat very specific areas and are hardly accessible to non-experts.

Therefore many researchers, including us, keep and cherish a collection of distances for use in their areas of science. In view of the growing general need for an accessible interdisciplinary source for a vast multitude of researchers, we have expanded our private collection into this Dictionary. Some additional material was reworked from various encyclopedias, especially Encyclopedia of Mathematics [ EM98], MathWorld [ Weis99], PlanetMath [ PM], and Wikipedia [ WFE ]. However, the majority of distances are extracted directly from specialist literature.

Besides distances themselves, we have collected many distance-related notions (especially in Chap. 1) and paradigms, enabling people from applications to get those (arcane for non-specialists) research tools, in ready-to-use fashion. This and the appearance of some distances in di ? erent contexts can be a source of new research.

In the time when over-specialization and terminology fences isolate researchers, this Dictionary tries to be “centripetal” and “ecumenical,” providing some access and altitude of vision but without taking the route of scienti ? c vulgarization. This attempted balance has de ? ned the structure and style of the Dictionary.

This reference book is a specialized encyclopedic dictionary organized by subject area. It is divided into 29 chapters grouped into seven parts of about the same length. The titles of the parts are purposely approximative: they allow a reader to ? gure out her / his area of interest and competence. For example, Parts II, III and IV, V require some culture in, respectively, pure and applied Mathematics. Part VII can be read by a layman.

The chapters are thematic lists, by areas of Mathematics or applications, which can be read independently. When necessary, a chapter or a section starts with a short introduction: a ? eld trip with the main concepts. Besides these introductions, the main properties and uses of distances are given, within items, in some instances. We also tried, when it was easy, to trace distances to their originator (s), but the proposed extensive bibliography has a less general ambition: just to provide convenient sources for a quick search.

Each chapter consists of items ordered in a way that hints of connections between them. All item titles and (with majiscules only for proper nouns) selected key terms can be traced in the large Subject Index; they are boldfaced unless the meaning is clear from the context. So, the de ? nitions are easy to locate, by subject, in chapters and/or, by alphabetic order, in the Subject Index.

The introductions and de ? nitions are reader-friendly and generally independent of each other; but they are interconnected, in the three-dimensional HTML manner, by hyperlink-like boldfaced references to similar de ? nitions.

Many nice curiosities appear in this “Who is Who” of distances. Examples of such sundry terms are: ubiquitous Euclidean distance (“as-the-crow - ? ies”), ? ower-shop metric (shortest way between two points, visiting a “? ower-shop” point ? rst), knight-move metric on a chessboard, Gordian distance of knots, Earth Mover distance, biotope distance, Procrustes distance, lift metric, Post O ? ce metric, Internet hop metric, WWW hyperlink quasi-metric, Moscow metric, and dogkeeper distance.

Besides abstract distances, the distances having physical meaning also appear (especially in Part VI); they range from 1.6 × 10-35 m (Planck length) to 4.3 × 1026 m (the estimated size of the observable Universe, about 27 × 1060 Planck lengths).

The number of distance metrics is infinite, and therefore our Dictionary cannot enumerate all of them. But we were inspired by several successful thematic dictionaries on other infinite lists; for example, on Numbers, Integer Sequences, Inequalities, Random Processes, and by atlases of Functions, Groups, Fullerenes, etc. On the other hand, the large scope often forced us to switch to the mode of laconic tutorial.

The target audience consists of all researchers working on some measuring schemes and, to a certain degree, students and a part of the general public interested in science.

We have tried to address, even if incompletely, all scienti ? c uses of the notion of distance. But some distances did not made it to this Dictionary due to space limitations (being too speci ? c and/or complex) or our oversight. In general, the size / interdisciplinarity cut-o ?, i.e., decision where to stop, was our main headache. We would be grateful to readers who send us their favorite distances missed here. Four pages at the end are reserved for such personal additions.

I. Mathematics of Distances

1. General Definitions

2. Topological Spaces

3. Generalizations of Metric Spaces

4. Metric Transforms

5. Metrics on Normed Structures



II. Geometry and Distances

6. Distances in Geometry

7. Riemannian and Hermitian Metrics

8. Distances on Surfaces and Knots

9. Distances on Convex Bodies, Cones, and Simplicial Complexes

III. Distances in Classical Mathematics

10. Distances in Algebra



11. Distances on Strings and Permutations

12. Distances on Numbers, Polynomials, and Matrices

13. Distances in Functional Analysis

14. Distances in Probability Theory

IV. Distances in Applied Mathematics

15. Distances in Graph Theory

16. Distances in Coding Theory

17. Distances and Similarities in Data Analysis

18. Distances in Mathematical Engineering

V. Computer-related Distances

19. Distances on Real and Digital Planes

20. Voronoi Diagram Distances

21. Image and Audio Distances

22. Distances in Internet and Similar Networks

VI. Distances in Natural Sciences

23. Distances in Biology

24. Distances in Physics and Chemistry

25. Distances in Geography, Geophysics, and Astronomy

26. Distances in Cosmology and Theory of Relativity

VII. Real-world Distances

27. Length Measures and Scales

28. Non-mathematical and Figurative Meaning of Distance



 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2006 DictionaryofDistancesMichel-Marie Deza
Elena Deza
Dictionary of Distances2006