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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:279893 |
| Date | January 1991 |
| Creators | Kay, Andrew |
| Contributors | McColl, William F. |
| Publisher | University of Oxford |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://ora.ox.ac.uk/objects/uuid:6765f1e6-e07c-4029-993f-a5b0d9657050 |
Page generated in 0.0018 seconds