[LAD] OT-ish: realtime 2d placement algorithms :-/

[Niels Mayer]

On Fri, Apr 30, 2010 at 3:10 PM, James Morris <james at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxaudio.org/pipermail/linux-audio-dev/attachments/20100430/7dcef413/attachment.html>