Site Search
Computer Science


Dr. Robert KentDr. Robert Kent
Dr. Robert Kent
Imran Ahmad, Ph.D.Dr. Imran Ahmad
Dr. Imran Ahmad
Christie Ezeife, Ph.D.Dr. Christie Ezeife
Dr. Christie Ezeife
Xiaobu Yuan, Ph.D.Dr. Xiaobu Yuan
Dr. Xiaobu Yuan
Dr. Scott GoodwinDr. Scott Goodwin
Dr. Scott Goodwin
Dr. Luis RuedaDr. Luis Rueda
Dr. Luis Rueda
Windsor WaterfrontWindsor Waterfront Park
Windsor Waterfront Park
Alioune Ngom, Ph.D.Dr. Alioune Ngom
Dr. Alioune Ngom
Arunita Jaekel, Ph.D.Dr. Arunita Jaekel
Dr. Arunita Jaekel
Dr. Ziad Kobti lecturingDr. Ziad Kobti
Dr. Ziad Kobti
Lambton TowerLambton Tower
Lambton Tower
Robin Gras, Ph.D.Dr. Robin Gras
Dr. Robin Gras
Jessica Chen, Ph.D.Dr. Jessica Chen
Dr. Jessica Chen

Structures from Distances in Two and Three Dimensions using Stochastic Proximity Embedding

Add this event into your calendar using the iCAL format
  • Fri, 12/01/2017 - 10:00am - 12:00pm

Structures from Distances in Two and Three Dimensions using Stochastic Proximity Embedding

MSc Thesis Defense by:

Udayamoorthy Navaneetha Krishnan

Date: Friday, December 1st, 2017
Time: 10:00 am – 12:00 pm
Location: 3105, Lambton Tower

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.

Thesis Committee:
Internal Reader:  Dr. Xiaobu Yuan    
External Reader:  Dr. Myron Hlynka
Advisors:  Dr. Asish Mukhopadhay and Dr. Yash P Aneja
Chair:  Dr. Imran Ahmad

See More: