nach oben

2014 | Buch

Encyclopedia of Distances

verfasst von: Michel Marie Deza, Elena Deza

Verlag: Springer Berlin Heidelberg

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This updated and revised third edition of the leading reference volume on distance metrics includes new items from very active research areas in the use of distances and metrics such as geometry, graph theory, probability theory and analysis. Among the new topics included are, for example, polyhedral metric space, nearness matrix problems, distances between belief assignments, distance-related animal settings, diamond-cutting distances, natural units of length, Heidegger’s de-severance distance, and brain distances.

The publication of this volume coincides with intensifying research efforts into metric spaces and especially distance design for applications. Accurate metrics have become a crucial goal in computational biology, image analysis, speech recognition and information retrieval.

Leaving aside the practical questions that arise during the selection of a ‘good’ distance function, this work focuses on providing the research community with an invaluable comprehensive listing of the main available distances.

As well as providing standalone introductions and definitions, the encyclopedia facilitates swift cross-referencing with easily navigable bold-faced textual links to core entries. In addition to distances themselves, the authors have collated numerous fascinating curiosities in their Who’s Who of metrics, including distance-related notions and paradigms that enable applied mathematicians in other sectors to deploy research tools that non-specialists justly view as arcane. In expanding access to these techniques, and in many cases enriching the context of distances themselves, this peerless volume is certain to stimulate fresh research.

Inhaltsverzeichnis

Frontmatter

Mathematics of Distances

Frontmatter

Chapter 1. General Definitions

Abstract

In this core Chapter, the main metrics and metric-related notions are given.

Michel Marie Deza, Elena Deza

Chapter 2. Topological Spaces

Abstract

Michel Marie Deza, Elena Deza

Chapter 3. Generalizations of Metric Spaces

Abstract

Some immediate generalizations of the notion of metric, for example, quasi-metric, near-metric, extended metric, were defined in Chap. 1. Here we give some generalizations in the direction of Topology, Probability, Algebra, etc.

Michel Marie Deza, Elena Deza

Chapter 4. Metric Transforms

Abstract

There are many ways to obtain new distances (metrics) from given distances (metrics). Metric transforms give new distances as a functions of given metrics (or given distances) on the same set X. A metric so obtained is called a transform metric. We give some important examples of transform metrics in Sect. 4.1.

Michel Marie Deza, Elena Deza

Chapter 5. Metrics on Normed Structures

Abstract

In this chapter we consider a special class of metrics defined on some normed structures, as the norm of the difference between two given elements. This structure can be a group (with a group norm), a vector space (with a vector norm or, simply, a norm), a vector lattice (with a Riesz norm), a field (with a valuation), etc.

Michel Marie Deza, Elena Deza

Geometry and Distances

Frontmatter

Chapter 6. Distances in Geometry

Abstract

Geometry arose as the field of knowledge dealing with spatial relationships. It was one of the two fields of pre-modern Mathematics, the other being the study of numbers.

Michel Marie Deza, Elena Deza

Chapter 7. Riemannian and Hermitian Metrics

Abstract

Riemannian Geometry is a multidimensional generalization of the intrinsic geometry of 2D surfaces in the Euclidean space \(\mathbb{E}^{3}\).

Michel Marie Deza, Elena Deza

Chapter 8. Distances on Surfaces and Knots

Abstract

A surface is a real 2D (two-dimensional) manifold M ², i.e., a Hausdorff space, each point of which has a neighborhood which is homeomorphic to a plane \(\mathbb{E}^{2}\), or a closed half-plane (cf. Chap. 7).

A compact orientable surface is called closed if it has no boundary, and it is called a surface with boundary, otherwise.

Michel Marie Deza, Elena Deza

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

Abstract

A convex body in the n-dimensional Euclidean space \(\mathbb{E}^{n}\) is a convex compact connected subset of \(\mathbb{E}^{n}\).

Michel Marie Deza, Elena Deza

Distances in Classical Mathematics

Frontmatter

Chapter 10. Distances in Algebra

Abstract

A group (G, ⋅ , e) is a set G of elements with a binary operation ⋅ , called the group operation, that together satisfy the four fundamental properties of closure (x ⋅ y ∈ G for any x, y ∈ G), associativity (x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z for any x, y, z ∈ G), the identity property (\(x \cdot e = e \cdot x = x\) for any x ∈ G), and the inverse property (for any x ∈ G, there exists an element x ⁻¹ ∈ G such that \(x \cdot x^{-1} = x^{-1} \cdot x = e\)

Michel Marie Deza, Elena Deza

Chapter 11. Distances on Strings and Permutations

Abstract

An alphabet is a finite set \(\mathcal{A}\), \(\vert \mathcal{A}\vert \geq 2\), elements of which are called characters (or symbols).

Michel Marie Deza, Elena Deza

Chapter 12. Distances on Numbers, Polynomials, and Matrices

Abstract

Here we consider the most important metrics on the classical number systems: the semiring \(\mathbb{N}\) of natural numbers, the ring \(\mathbb{Z}\) of integers, and the fields \(\mathbb{Q}\), \(\mathbb{R}\), \(\mathbb{C}\) of rational, real, complex numbers, respectively.

Michel Marie Deza, Elena Deza

Chapter 13. Distances in Functional Analysis

Abstract

Functional Analysis is the branch of Mathematics concerned with the study of spaces of functions. This usage of the word functional goes back to the calculus of variations which studies functions whose argument is a function. In the modern view, Functional Analysis is seen as the study of complete normed vector spaces, i.e., Banach spaces.

Michel Marie Deza, Elena Deza

Chapter 14. Distances in Probability Theory

Abstract

A probability space is a measurable space \((\Omega,\mathcal{A},P)\), where \(\mathcal{A}\) is the set of all measurable subsets of \(\Omega \), and P is a measure on \(\mathcal{A}\) with \(P(\Omega ) = 1\). The set \(\Omega \) is called a sample space.

Michel Marie Deza, Elena Deza

Distances in Applied Mathematics

Frontmatter

Chapter 15. Distances in Graph Theory

Abstract

A graph is a pair G = (V, E), where V is a set, called the set of vertices of the graph G, and E is a set of unordered pairs of vertices, called the edges of the graph G. A directed graph (or digraph) is a pair D = (V, E), where V is a set, called the set of vertices of the digraph D, and E is a set of ordered pairs of vertices, called arcs of the digraph D.

Michel Marie Deza, Elena Deza

Chapter 16. Distances in Coding Theory

Abstract

Coding Theory deals with the design and properties of error-correcting codes for the reliable transmission of information across noisy channels in transmission lines and storage devices. The aim of Coding Theory is to find codes which transmit and decode fast, contain many valid code words, and can correct, or at least detect, many errors. These aims are mutually exclusive, however; so, each application has its own good code.

Michel Marie Deza, Elena Deza

Chapter 17. Distances and Similarities in Data Analysis

Abstract

A data set is a finite set comprising m sequences \((x_{1}^{j},\ldots,x_{n}^{j})\), \(j \in \{ 1,\ldots,m\}\), of length n. The values \(x_{i}^{1},\ldots,x_{i}^{m}\) represent an attribute S _i.

Michel Marie Deza, Elena Deza

Chapter 18. Distances in Systems and Mathematical Engineering

Abstract

In this chapter we group the main distances used in Systems Theory (such as Transition Systems, Dynamical Systems, Cellular Automata, Feedback Systems) and other interdisciplinary branches of Mathematics, Engineering and Theoretical Computer Science (such as, say, Robot Motion and Multi-objective Optimization).

Michel Marie Deza, Elena Deza

Computer-Related Distances

Frontmatter

Chapter 19. Distances on Real and Digital Planes

Abstract

Any L _p -metric (as well as any norm metric for a given norm | | . | | on \(\mathbb{R}^{2}\)) can be used on the plane \(\mathbb{R}^{2}\), and the most natural is the L ₂-metric, i.e., the Euclidean metric \(d_{E}(x,y) = \sqrt{(x_{1 } - y_{1 } )^{2 } + (x_{2 } - y_{2 } )^{2}}\) which gives the length of the straight line segment [x, y], and is the intrinsic metric of the plane.

Michel Marie Deza, Elena Deza

Chapter 20. Voronoi Diagram Distances

Abstract

Given a finite set A of objects A _i in a space S, computing the Voronoi diagram of A means partitioning the space S into Voronoi regions V (A _i) in such a way that V (A _i) contains all points of S that are “closer” to A _i than to any other object A _j in A.

Michel Marie Deza, Elena Deza

Chapter 21. Image and Audio Distances

Abstract

Image Processing treats signals such as photographs, video, or tomographic output. In particular, Computer Graphics consists of image synthesis from some abstract models, while Computer Vision extracts some abstract information: say, the 3D description of a scene from video footage of it. From about 2000, analog image processing (by optical devices) gave way to digital processing, and, in particular, digital image editing (for example, processing of images taken by popular digital cameras).

Michel Marie Deza, Elena Deza

Chapter 22. Distances in Networks

Abstract

A network is a graph, directed or undirected, with a positive number (weight) assigned to each of its arcs or edges. Real-world complex networks usually have a gigantic number N of vertices and are sparse, i.e., with relatively few edges.

Michel Marie Deza, Elena Deza

Distances in Natural Sciences

Frontmatter

Chapter 23. Distances in Biology

Abstract

Distances are mainly used in Biology to pursue basic classification tasks, for instance, for reconstructing the evolutionary history of organisms in the form of phylogenetic trees. In the classical approach those distances were based on comparative morphology, physiology, mating studies, paleontology and immunodiffusion. The progress of modern Molecular Biology also allowed the use of nuclear- and amino-acid sequences to estimate distances between genes, proteins, genomes, organisms, species, etc.

Michel Marie Deza, Elena Deza

Chapter 24. Distances in Physics and Chemistry

Abstract

Physics studies the behavior and properties of matter in a wide variety of contexts, ranging from the submicroscopic particles from which all ordinary matter is made (Particle Physics) to the behavior of the material Universe as a whole (Cosmology).

Michel Marie Deza, Elena Deza

Chapter 25. Distances in Earth Science and Astronomy

Abstract

In Geography, spatial scales are shorthand terms for distances, sizes and areas. For example, micro, meso, macro, mega may refer to local (0.001–1), regional (1–100), continental (100–10,000), global ( > 10,000) km, respectively.

Michel Marie Deza, Elena Deza

Chapter 26. Distances in Cosmology and Theory of Relativity

Abstract

The Universe is defined as the whole space-time continuum in which we exist, together with all the energy and matter within it.

Michel Marie Deza, Elena Deza

Real-World Distances

Frontmatter

Chapter 27. Length Measures and Scales

Abstract

The term length has many meanings: distance, extent, linear measure, span, reach, end, limit, etc.; for example, the length of a train, a meeting, a book, a trip, a shirt, a vowel, a proof. The length of an object is its linear extent, while the height is the vertical extent, and width (or breadth) is the side-to-side distance at 90^∘ to the length, wideness. The depth is the distance downward, distance inward, deepness, profundity, drop.

Michel Marie Deza, Elena Deza

Chapter 28. Distances in Applied Social Sciences

Abstract

In this chapter we present selected distances used in real-world applications of Human Sciences. In this and the next chapter, the expression of distances ranges from numeric (say, in m) to ordinal (as a degree assigned according to some rule) and nominal.

Michel Marie Deza, Elena Deza

Chapter 29. Other Distances

Abstract

In this chapter we group together distances and distance paradigms which do not fit in the previous chapters, being either too practical (as in equipment), or too general, or simply hard to classify.

Michel Marie Deza, Elena Deza

Backmatter

Titel: Encyclopedia of Distances
verfasst von: Michel Marie Deza
Elena Deza
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-44342-2
Print ISBN: 978-3-662-44341-5
DOI: https://doi.org/10.1007/978-3-662-44342-2