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.

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)