@inproceedings{5dbfb81106ef408d8c309a1725ba8416,
title = "Optimal algorithms for two-dimensional box placement problems",
abstract = "The two-dimensional box placement problem involves finding a position to place a rectangular box into a container given n rectangular boxes that have already been placed. It commonly arises as a subproblem in many algorithms for cutting stock and packing problems. We develop an asymptotically optimal approach for finding the bottom-leftmost feasible position, and modify it to find all normal feasible positions (which is also asymptotically optimal). Our approach relies on augmented versions of the segment tree data structure, and is simpler and more practicable than the best existing approach. Furthermore, it does not require that the placed boxes are interior-disjoint. {\textcopyright} 2011 Springer-Verlag.",
keywords = "box placement, combinatorial optimization, cutting and packing, rectangle placement, VLSI layout",
author = "Wenbin Zhu and Wee-Chong Oon and Yujian Weng and Andrew Lim",
year = "2011",
doi = "10.1007/978-3-642-21827-9\_25",
language = "English",
isbn = "9783642218262",
volume = "6704 LNAI",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "246--255",
booktitle = "Modern Approaches in Applied Intelligence",
address = "Germany",
edition = "PART 2",
note = "24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011 ; Conference date: 28-06-2011 Through 01-07-2011",
}