Abstract

Inspired by air-traffic control and other applications where moving objects have to be labeled, we consider the following (static) point-labeling problem: given a set P of n points in the plane and labels that are unit squares, place a label with each point in P in such a way that the number of free labels (labels not intersecting any other label) is maximized. We develop efficient constant-factor approximation algorithms for this problem, as well as PTASs, for various label-placement models.


Original document

The different versions of the original document can be found in:

http://dx.doi.org/10.1007/978-3-642-13731-0_28
https://api.elsevier.com/content/article/PII:S0925772111000800?httpAccept=text/plain,
http://dx.doi.org/10.1016/j.comgeo.2011.10.004 under the license https://www.elsevier.com/tdm/userlicense/1.0/
https://www.win.tue.nl/~mdberg/Papers/2010/bg-aaflm-eurocg-10.pdf,
https://link.springer.com/chapter/10.1007/978-3-642-13731-0_28,
https://www.narcis.nl/publication/RecordID/oai%3Apure.tue.nl%3Apublications%2Fdf4f0ffc-36e8-45ea-a768-a1dd37dd3010,
http://ui.adsabs.harvard.edu/abs/2010LNCS.6139..297D/abstract,
https://doi.org/10.1007/978-3-642-13731-0_28,
http://alexandria.tue.nl/openaccess/Metis239508.pdf,
https://rd.springer.com/chapter/10.1007/978-3-642-13731-0_28,
https://academic.microsoft.com/#/detail/2110919917
https://www.narcis.nl/publication/RecordID/oai%3Apure.tue.nl%3Apublications%2F77caa8cb-6272-4880-b521-52acf79ba904,
https://dblp.uni-trier.de/db/journals/comgeo/comgeo45.html#BergG12,
https://dl.acm.org/citation.cfm?id=2109239.2109581,
https://doi.org/10.1016/j.comgeo.2011.10.004,
https://research.tue.nl/en/publications/approximation-algorithms-for-free-label-maximization-3,
https://academic.microsoft.com/#/detail/2030174981



DOIS: 10.1016/j.comgeo.2011.10.004 10.1007/978-3-642-13731-0_28

Back to Top

Document information

Published on 31/12/09
Accepted on 31/12/09
Submitted on 31/12/09

Volume 2010, 2010
DOI: 10.1016/j.comgeo.2011.10.004
Licence: Other

Document Score

0

Views 2
Recommendations 0

Share this document

claim authorship

Are you one of the authors of this document?