[MUD-Dev] Finding Space

[Ned Lovely]

> :A friend of mine glanced at this problem and said, "Oh, that's a
> :bin-stuffing problem."  Of course, he didn't remember anything else
> :about the problem, so here I am. :)
> Also called "bin packing", I believe. Not something I know anything about.

Well, I dug out my generic algorithm tome, and I found that one of the
questions in the chapter on approximations deals with bin packing. This
is from "Introduction to Algorithms," by Cormen, Leiserson, and Rivest, MIT
Press, 1990.

I'm going to use () for subscripts, and I'll type out the summation in English
instead of trying to draw it ;)

----
37-1 Bin Packing
Suppose that we are given a set of n objects, where the size s(i) of the
ith object satisfies 0 < s(i) < 1. We wish to pack all the objects into the
minimum number of unit-sized bins. Each bin can hold any subset of the
objects whose total size does not exceed 1.

a. PRove that the problem of determining the minimum number of bins required
is NP-Hard. (Hint: Reduce from the subset-sum problem.)

The first-fit heuristic takes each object in turn and places it into the
first bin that can accommadate it. Let S = (the sum from i=1 to n of s(i)).

b. Argue that the optimal number of bins required is at least ceiling(S).

c. Argue that the first-fit heuristic leaves at most one bin less than half
full.

d. PRove that the number of bins used by the first-fit heuristic is never
more than ceiling(2S).

e. Prove a ratio bound of 2 for the first fit heuristic.

f. Give an efficient implementation of the first fit heuristic, and analyze
its running time.

----

Any mistakes are, of course, mine in the transcription...

Doesn't sound like ensuring non-collision in a 3-D space is a bin stuffing
problem...

As a quick guess, the fastest way to to it would be to give each object a
center. Cache the distance from the center to the farthest out point on that
object. To check for collision, measure the distance from center-to-center,
and compare it to how much space the objects need. If it is greater, you're
golden. If it's closer, do something a lot ickier... I can think of ways to
do it in 2-D space, but generalizing it to #-D space feels ugly.

> :Does anyone have the answer? :)
> Well, this is beginning to sound a *lot* like Winograd's "Blocks World".
> He got a PhD degree for implementing that!

I dug up a URL that looked kinda interesting. Do you have a pointer to a good
site/paper for that?

Well, since this is my first message, I should give a little bit of an
introduction.

I've been interested in muds ever since a local 8-line BBS ran a circle for
its subscribers. I've always been fascinated with how people communicated,
and I was impressed by the potential for strange and interesting interaction.

Right now, I'm looking for someone to hand me specs for a mud so that I can 
just write it. I know I can write module-level code, and I've got more theory
on OO design than I could shake a stick at. I figure I should actually do
something with it.

--
njl