Return to search

Angle and distance geometry problems

Distance geometry problems (DGPs) are concerned with the construction of structures given partial information about distances between vertices. I present a generalisation which I call the angle and distance geometry problem (ADGP), in which partial angle information may be given as well. The work is primarily concerned with the algebraic and theoretical aspects of this problem, although it contains some information on practical applications. The embedding space is typically real three dimensional space for applications such as computer aided design and molecular chemistry, although other embedding spaces are possible. I show that both DGP and ADGP are NP-hard, but that in some sense the ADGP is more expressive than the DGP. To combat the problems of NP-hardness I present some graph theoretic heuristics which may be applied to both DGP and ADGP, and so reduce the time required by general purpose algorithms for their solution. I discuss the general purpose algorithms Cylindrical Algebraic Decomposition and Gröbner bases and their application to this field. In addition, I present an O(n) parallel algorithm for computing convex hulls in three dimensions, using O(n<sup>2</sup>) processors connected in a mesh-like topology with no shared memory.

Identiferoai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:279893
Date January 1991
CreatorsKay, Andrew
ContributorsMcColl, William F.
PublisherUniversity of Oxford
Source SetsEthos UK
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation
Sourcehttp://ora.ox.ac.uk/objects/uuid:6765f1e6-e07c-4029-993f-a5b0d9657050

Page generated in 0.0123 seconds