home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / sources / wanted / 4991 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  1.3 KB
  1. Xref: sparky comp.sources.wanted:4991 comp.graphics:11691
  2. Newsgroups: comp.sources.wanted,comp.graphics
  3. Path: sparky!uunet!news.smith.edu!orourke
  4. From: orourke@sophia.smith.edu (Joseph O'Rourke)
  5. Subject: Re: area optimization algorithm
  6. Message-ID: <1992Nov10.185409.16394@sophia.smith.edu>
  7. Organization: Smith College, Northampton, MA, US
  8. References: <1992Nov10.165921.11772@infonode.ingr.com>
  9. Date: Tue, 10 Nov 1992 18:54:09 GMT
  10. Lines: 20
  11.  
  12. In article <1992Nov10.165921.11772@infonode.ingr.com> maverick@topgun.b29.ingr.com writes:
  13. >I would like to know if anyone can point me to a source of any kind (book,
  14. >ftp site, etc.) that has an algorithm for area optimization. [...]
  15. >Basically, the problem is: given 'X' number of rectangles, place them within
  16. >a given area, with a minimum amount of space left unused in between the
  17. >rectangles.
  18.  
  19. The keywords for this topic are "bin packing," and more specificially,
  20. "two-dimensional bin packing,"  the "stock cutting problem,"
  21. and "automatic marker making." It has been studied extensively.  
  22. Most variations of the problem are fundamentally intractable (NP-complete), 
  23. but approximation algorithms are known.
  24.  
  25. @book{P.S
  26. , author =    "C. H. Papadimitriou and K. Steiglitz"
  27. , title =    "Combinatorial Optimization: Algorithms and Complexity"
  28. , publisher =    "Prentice Hall"
  29. , address =    "Englewood Cliffs, NJ"
  30. , year =    1982
  31. }
  32.