Labeling points with given rectangles

Abstract

In this paper, we consider the following problem: Given n pairs of a point and an axis-parallel rectangle in the plane, place each rectangle at each point in order that the point lies on the corner of the rectangle and the rectangles do not intersect. If the size of the rectangles may be enlarged or reduced at the same factor, maximize the factor. This paper generalizes the results of Formann and Wagner [Proc. 7th Annual ACM Symp. on Comput. Geometry (SoCG'91), 1991, pp. 281-288]. They considered the uniform squares case and showed that there is no polynomial time algorithm less than 2-approximation. We present a 2-approximation algorithm of the non-uniform rectangle case which runs in 0(n(2) log n) time and takes 0(n(2)) space. We also show that the decision problem can be solved in 0(n log n) time and space in the RAM model by transforming the problem to a simpler geometric problem. (C) 2003 Elsevier B.V. All rights reserved.