# zbMATH — the first resource for mathematics

A dynamic algorithm for placing rectangles without overlapping. (English) Zbl 0764.68182
Summary: We consider the dynamic allocation problem of rectangles such that a mixed sequence of insertions and deletions of rectangles in a rectangular board is executed without any pair of rectangle overlapping each other. We present an $$O(n\log\log n)$$ time algorithm for insertion of a rectangle if $$n$$ rectangles have been already placed in the board. We solve the problem by reducing it to the contour construction problem on a spatial class of arrangements of rectangles.

##### MSC:
 68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
##### Keywords:
dynamic allocation of rectangles