Labeling points with given rectangles

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...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2004-02, Vol.89 (3), p.115-121
Main Authors: Jung, Joo-Won, Chwa, Kyung-Yong
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Approximation
Approximation algorithms
Artificial intelligence
Computational geometry
Computer science
control theory
systems
Exact sciences and technology
Geometry
Map labeling
Pattern recognition. Digital image processing. Computational geometry
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 O( n 2log n) time and takes O( n 2) space. We also show that the decision problem can be solved in O( nlog n) time and space in the RAM model by transforming the problem to a simpler geometric problem.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2003.09.017