Labeling points with given rectangles

Cited 6 time in webofscience Cited 11 time in scopus
  • Hit : 592
  • Download : 0
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.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2004-02
Language
English
Article Type
Article
Citation

INFORMATION PROCESSING LETTERS, v.89, no.3, pp.115 - 121

ISSN
0020-0190
DOI
10.1016/j.ipl.2003.09.017
URI
http://hdl.handle.net/10203/82928
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 6 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0