Get all the updates for this publication

Journal

Optimal algorithm for a special point-labeling problemPublished in ELSEVIER SCIENCE BV

2004

Volume: 89

Issue: 2

Pages: 91 - 98

A special class of map labeling problem is studied. Let P = {p 1,p2,...,pn} be a set of point sites distributed on a 2D map. A label associated with each point pi is an axis-parallel rectangle ri of specified width. The height of all ri,i = 1,2,...,n are same. The placement of ri must contain pi at its top-left or bottom-left corner, and it does not obscure any other point in P. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. We first consider a simple model for this problem. Here, for each point p i, the corner specification (i.e., whether the point pi would appear at the top-left or bottom-left corner of the label) is known a priori. We show that the time complexity of this problem is Ω(n log n), and then propose an algorithm for this problem which runs in O(n log n) time. If the corner specifications of the points in P are not known, our algorithm is a 2-approximation algorithm. Here we propose an efficient heuristic algorithm that is easy to implement. Experimental evidences show that it produces optimal solutions for most of the randomly generated instances and for all the standard benchmarks available in http://www.math-inf.uni-greifswald.de/map-labeling/. © 2003 Elsevier B.V. All rights reserved.

Content may be subject to copyright.

About the journal

Journal | Data powered by TypesetInformation Processing Letters |
---|---|

Publisher | Data powered by TypesetELSEVIER SCIENCE BV |

ISSN | 0020-0190 |