Euclidean Distance Geometry

An Introduction

verfasst von: Dr. Leo Liberti, Prof. Dr. Carlile Lavor

Verlag: Springer International Publishing

Buchreihe : Springer Undergraduate Texts in Mathematics and Technology

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

Einloggen, um Zugang zu erhalten

Über dieses Buch

This textbook, the first of its kind, presents the fundamentals of distance geometry: theory, useful methodologies for obtaining solutions, and real world applications. Concise proofs are given and step-by-step algorithms for solving fundamental problems efficiently and precisely are presented in Mathematica®, enabling the reader to experiment with concepts and methods as they are introduced. Descriptive graphics, examples, and problems, accompany the real gems of the text, namely the applications in visualization of graphs, localization of sensor networks, protein conformation from distance data, clock synchronization protocols, robotics, and control of unmanned underwater vehicles, to name several. Aimed at intermediate undergraduates, beginning graduate students, researchers, and practitioners, the reader with a basic knowledge of linear algebra will gain an understanding of the basic theories of distance geometry and why they work in real life.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Motivation

Abstract

This book is a basic introduction to Distance Geometry (DG): it gives an overview of the mathematical theory of DG. Our point of view derives from our motivation to apply DG methods to the problem of finding the structure of proteins given some of the interatomic distances.

Leo Liberti, Carlile Lavor

Chapter 2. The Distance Geometry Problem

Abstract

The Distance Geometry Problem (DGP) is an inverse problem. The corresponding “direct problem” is to compute some pairwise distances of a given set of points. Whereas the direct problem is obviously trivial (just carry out the computation), the inverse problem is generally difficult to solve.

Leo Liberti, Carlile Lavor

Chapter 3. Realizing complete graphs

Abstract

In this chapter, we consider the DGP on a very specific class of graphs: the (K + 1)-cliques, i.e., complete graphs on K + 1 vertices, where K is the dimension of the embedding space \(\mathbb {R}^{K}\).

Leo Liberti, Carlile Lavor

Chapter 4. Discretizability

Abstract

We remarked in Sect. 2.5.1 that direct methods, which search for solutions in the continuous space \(\mathbbm {R}^{Kn}\) of all realizations, do not always work all that well. In Chap. 3, we discussed a discrete method for realizing complete graphs in polytime. In this chapter, we look at larger classes of graphs for which the search space can be shown to be discrete.

Leo Liberti, Carlile Lavor

Chapter 5. Molecular distance geometry problems

Abstract

The Molecular Distance Geometry Problem (MDGP) [86] is the subclass of DGP instances with K=3. Since the DGP is NP-hard for each K [107], the MDGP is also NP-hard.

Leo Liberti, Carlile Lavor

Chapter 6. Vertex orders

Abstract

In this chapter, we address the question: given a graph, does it have a trilateration order? And if so, is it contiguous? Unlike the DGP, which is not known to be in NP, these order existence problems are both in NP: if a graph is a YES instance, a suitable vertex order can be verified to be correct in polytime, by simply checking that it has enough adjacent predecessors.

Leo Liberti, Carlile Lavor

Chapter 7. Flexibility and rigidity

Abstract

In this chapter we discuss rigidity and flexibility of graph frameworks

Leo Liberti, Carlile Lavor

Chapter 8. Approximate realizations

Abstract

In this chapter, we propose some methods for realizing large graphs. These methods do not explicitly rely on the adjacency structure of the graph, and are mostly based on linear algebra.

Leo Liberti, Carlile Lavor

Chapter 9. Taking DG further

Abstract

We wrote this last chapter in order to give our readers some sense of the direction that the DG field is taking today.

Leo Liberti, Carlile Lavor

Backmatter

Titel: Euclidean Distance Geometry
verfasst von: Dr. Leo Liberti
Prof. Dr. Carlile Lavor
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-60792-4
Print ISBN: 978-3-319-60791-7
DOI: https://doi.org/10.1007/978-3-319-60792-4