Consider a space of finite area (for eg., a rectangle). We need to pack circles of fixed radius in this finite area. Note that the position (coordinates) of every circle in space is given and fixed.
Two circles cannot be packed in the same rectangle if their areas overlap. Is there an algorithm with provable guarantees that minimizes the number of rectangles that we need to pack all the circles?
What is the best online variant of this algorithm? We can consider extensions of first fit, best fit, etc., to this problem. Are there any guarantees on their performance?