4 ms·
Soap films approximate minimum spanning trees. See: http://csunplugged.org/sites/default/files/activity_pdfs_full/unplugged-15-steiner_trees_0.pdf http://csunp
by rfreytag 14y ago
Soap films approximate minimum spanning trees. See: http://csunplugged.org/sites/default/files/activity_pdfs_full/unplugged-15-steiner_trees_0.pdf http://csunplugged.org/sites/default/files/activity_pdfs_ful... (see page 7 [aka, page 157]).
Actually, these films approximate Steiner Trees; which is harder (NP-complete): https://en.wikipedia.org/wiki/Steiner_tree_problem https://en.wikipedia.org/wiki/Steiner_tree_problem
EDIT: replaced 'find' and 'solve' with 'approximate.'
EDIT: added '(NP-complete)'.
- VMG 14y agoAlso featured in this video: http://www.youtube.com/watch?v=dAyDi1aa40E http://www.youtube.com/watch?v=dAyDi1aa40E
- jerf 14y agoOnly for sufficiently small definitions of "solve": http://arxiv.org/pdf/quant-ph/0502072v2 http://arxiv.org/pdf/quant-ph/0502072v2 Definitions which turn out to be very small indeed.
- Dn_Ab 14y agoHarder is an understatement =) The bubbles don't solve Steiner Trees per se, they just give decent approximations. They are susceptible to local minimums. Scott Aaronson has given demonstrations against these claims.