Date of Award

2017

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Degree of Freedom Approach; Distance Geometry Problem; Distance Matrix Completion Approach; Molecular Distance Geometry Problem; Point Placement Problem; Stochastic Proximity Embedding

Supervisor

Mukhopadhyay, Asish

Supervisor

Aneja, Yash

Rights

info:eu-repo/semantics/openAccess

Abstract

The point placement problem is to determine the locations of a set of distinct points uniquely (up to translation and reflection) by making the fewest possible pairwise distance queries of an adversary. Deterministic and randomized algorithms are available if distances are known exactly. In this thesis, we discuss a 1-round algorithm for approximate point placement in the plane in an adversarial model. The distance query graph presented to the adversary is chordal. The remaining distances are uniquely determined using the Stochastic Proximity Embedding (SPE) method due to Agrafiotis, and the layout of the points is also generated from SPE. We have also computed the distances uniquely using a distance matrix completion algorithm for chordal graphs, based on a result by Bakonyi and Johnson. The layout of the points is determined using the traditional Young- Householder approach. We compared the layout of both the method and discussed briefly inside. The modified version of SPE is proposed to overcome the highest translation embedding that the method faces when dealing with higher learning rates. We also discuss the computation of molecular structures in three-dimensional space, with only a subset of the pairwise atomic distances available. The subset of distances is obtained using the Philips model for creating artificial backbone chain of molecular structures. We have proposed the Degree of Freedom Approach to solve this problem and carried out our implementation using SPE and the Distance matrix completion Approach

Download

Share

COinS