I have a connected, sparse, graph (a molecule to be specific) and I'm interested in associating 3D coordinates with the vertices. Here's the kicker: I already have coordinates for none/some/all vertices which are not to be changed. The case of no coordinates I can solve with e.g. MDS, and the case where I have all coordinates is trivial.

In addition, I have a length associated with every edge which should be respected (but some distortion is fine). If it helps, I also have information about some (not all) angles and dihedral angles. Finally, all vertices should be separated as much as possible from one another. If need be, you may assume a maximum degree of ~6.

I don't expect a fully worked solution, but any pointers to literature would already be greatly appreciated!

New contributor
pckroon is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 1
    $\begingroup$ Maybe write down the energy function and perform simulated annealing? $\endgroup$ – Bullet51 Jul 11 at 15:55
  • $\begingroup$ Thanks for the input, I'll give that a try. Although it feels somewhat unsatisfactory ;) $\endgroup$ – pckroon Jul 12 at 13:25
  • $\begingroup$ There're lots of optimization algorithms to try, not only limited to simulated annealing. $\endgroup$ – Bullet51 Jul 12 at 16:22
  • $\begingroup$ Don't worry, I realize. The first thing I'll try will be some local optimization, preferably one I can take from scipy. But that's more StackOverflow than MathOverflow. $\endgroup$ – pckroon yesterday

There are a number of papers by Mike Treacy (I. Rivin is a co-author on some) which address this problem, but in a purely practical manner, using essentially the scheme proposed by Bullet51. Here is one:

Enumeration of periodic tetrahedral frameworks
M Treacy, KH Randall, S Rao, JA Perry, DJ Chadi
Zeitschrift fur Kristallographie 212 (11), 768-791

Your Answer

pckroon is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.