I'm having trouble understanding Chazelle's algorithm ,which is discussed in this paper The bottom-left bin-packing heuristic: an efficient implementation by B. Chazelle (1983), especially in implementing and updating the "F-data structure".

I can't quite get what Chazelle means by saying that F is a tree-representation of a rectilinear polygon. I thought the paper described a rectilinear polygon is presented by a list of "leftmost edges" rather a tree.

Also, when updating the data structure (section II.C) in the case in which the placement of a rectangle divides the current subhole into two new subholes, how could we know if the current subhole is divided and how can we add the subhole across the rectangle to the "F data structure"?

I really appreciate any help you can provide.

  • $\begingroup$ I am sorry that cannot help. But, am looking for solution to it and other paper (for bin packing problem, that I consider better) :On genetic algorithms for the packing of polygons, by Stefan Jakobs. I request you if have made progress on your question. $\endgroup$ – jiten Mar 31 '19 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.