Constant Approximation Algorithms for Knapsack and Bin Packing for Convex PolygonsResearch Paper
Geometric knapsack asks which objects of a given family fit together in a limited region. It models cutting and nesting problems, where allowing rotations can improve material use. For axis-aligned rectangles, with or without quarter turns, constant-factor approximations have long been known. Under arbitrary rotations the problem was much less understood:…