On Fri, Apr 30, 2010 at 3:10 PM, James Morris <james@jwm-art.net> wrote:
http://stackoverflow.com/questions/2746590/fast-block-placement-algorithm-advice-needed
 
Sounds implicitly, NP-Hard, and complexity-equivalent of computing a minimum spanning tree ( http://en.wikipedia.org/wiki/Minimum_spanning_tree ) or various packing problems ( http://en.wikipedia.org/wiki/Packing_problem http://en.wikipedia.org/wiki/Bin_packing_problem ).

Typical solutions include greedy approximation algorithms like  http://en.wikipedia.org/wiki/Bin_packing_problem#First-fit_algorithm . ... Consider also that this same class of problem is  routinely solved in nature in linear time, and often in less than an eyeblink. Therefore consider heuristics that nature might use to solve such problems, such as http://en.wikipedia.org/wiki/Simulated_annealing or the similar concept of "soap-bubble-computer" ( http://en.wikipedia.org/wiki/Surface_tension#Liquid_surface_as_a_computer ).

You mention "Bin Packing algorithms: their emphasis on optimal fit does not match the requirements of this algorithm."
The first-fit algo is one of many http://en.wikipedia.org/wiki/Approximation_algorithm used to solve these class of probems -- they are "optimizing" for fit, but as an approximation, they don't really have "an emphasis on optimal fit"; they have an emphasis on completing their computation before the universe ends. :-)

Niels
http://nielsmayer.com