Andy's Math/CS page

Monday, December 24, 2007

That's a Wrap

I had some gift-giving duties to attend to today... halfway into the wrapping phase, my mind wandered in a predictable direction:

Given a set of rectangular box dimensions, what is the smallest amount of paper that will wrap the box?

One would assume we want to cut out a rectangle of wrapping paper, since otherwise we get annoying scraps (and also the problem is mathematically trivial if we can cut a cross-type shape).

I haven't had any time to toy with this problem, but I had a feeling one particular MIT dude might have... and I was right. True to form, Erik Demaine delivers a whole page about various wrapping problems he's explored with colleagues.

To anyone reading who teaches a programming course, I would suggest that a fun algorithms assignment could be spun out problems of the above type. If the program outputted folding instructions too, so much the better.

Happy holidays, all!

Labels: ,

3 Comments:

  • Link?

    By Anonymous Anonymous, at 9:48 AM  

  • Sorry about that... (link added)

    By Blogger Andy D, at 11:17 AM  

  • At least you thought about this on Christmas eve. It was interesting to think about on Christmas morning when I was wrapping presents myself...

    By Blogger Steve, at 7:57 AM  

Post a Comment

<< Home