Arranging Rectangles in Smallest Area
- From: "Herbert Glarner" <herbert.glarner@xxxxxxxxxx>
- Date: Thu, 17 Aug 2006 09:20:23 +0200
Given is a non-empty disjoint set of orthogonal rectangles with (not
neccessarily unique) dimensions.
Searched is the arrangement to place all rectangles into a rectangular area
(of potentially infinite dimensions) such, that the /area/ of the the
resulting rectangle is minimized.
Note, that this is not the classical "bin packing problem", as the "bin"
(resulting rectangle) is not of a fixed size. It might be a specialization
of the "cutting stock problem", although it does not explicitely ask for
finding the minimal wasted space. (Also possible that the problem has an own
name, which I was not able to determine.) In any case it seems to be
NP-complete.
How would one approach this problem somewhat efficiently? I'd appreciate any
pointers.
Kind regards
//Herbert Glarner
.
- Prev by Date: Re: Is it essential to learn data structures before automata theory?
- Next by Date: averaging technique
- Previous by thread: HOTI 14 registration deadline extended until August 17, 2006
- Next by thread: averaging technique
- Index(es):
Relevant Pages
|
