Site Search
Computer Science


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

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

Add this event into your calendar using the iCAL format
  • Mon, 08/14/2017 - 11:00am - 1:00pm

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

MSc Thesis Proposal by:

Udayamoorthy Navaneetha Krishnan

Date:  Monday, August 14th, 2017
Time:  11: 00 am – 1: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 proposal, 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 a distance matrix completion algorithm for chordal graphs, based on a result by Bakonyi and Johnson. The layout of the points is determined from the complete distance matrix in two ways: using the traditional Young- Householder approach as well as a Stochastic Proximity Embedding (SPE) method due to Agrafiotis. We have also experimented with applying the SPE method directly to the partial distance matrix, bypassing the distance matrix completion algorithm altogether.

 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 More and Wu's lattice model for creating artificial instances of molecular structures. We have carried out initial experiments in applying the SPE technique to this problem also.

Thesis Committee:
Internal Reader: Dr. Xiaobu Yuan
External Reader: Dr. Myron Hlynka
Advisors: Dr. Asish Mukhopadhyay and Dr. Yash P Anega

See More: