Site Search
Computer Science

Photos

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

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

 

 



csgradinfo@uwindsor.ca
(519)253-3000


See More: