Approximation algorithms for free-label maximization

M.T. Berg, de; D.H.P. Gerrits

doi:10.1016/j.comgeo.2011.10.004

Approximation algorithms for free-label maximization

M.T. Berg, de, D.H.P. Gerrits

Algorithms

Research output: Contribution to journal › Article › Academic › peer-review

10 Citations (Scopus)

1 Downloads (Pure)

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 language	English
Pages (from-to)	153-168
Journal	Computational Geometry
Volume	45
Issue number	4
DOIs	https://doi.org/10.1016/j.comgeo.2011.10.004
Publication status	Published - 2012

Access to Document

10.1016/j.comgeo.2011.10.004

Cite this

@article{77caa8cb62724880b52152acf79ba904,

title = "Approximation algorithms for free-label maximization",

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

author = "{Berg, de}, M.T. and D.H.P. Gerrits",

year = "2012",

doi = "10.1016/j.comgeo.2011.10.004",

language = "English",

volume = "45",

pages = "153--168",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Approximation algorithms for free-label maximization

AU - Berg, de, M.T.

AU - Gerrits, D.H.P.

PY - 2012

Y1 - 2012

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

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

U2 - 10.1016/j.comgeo.2011.10.004

DO - 10.1016/j.comgeo.2011.10.004

M3 - Article

SN - 0925-7721

VL - 45

SP - 153

EP - 168

JO - Computational Geometry

JF - Computational Geometry

IS - 4

ER -

Approximation algorithms for free-label maximization

Abstract

Access to Document

Fingerprint

Cite this