Approximation algorithms for free-label maximization

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

1 Citation (Scopus)


Inspired by 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 languageEnglish
Title of host publicationAbstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)
EditorsJ. Vahrenhold
Place of PublicationDortmund
PublisherTechnische Universität Dortmund
Publication statusPublished - 2010
Event26th European Workshop on Computational Geometry (EuroCG 2010) - Dortmund
Duration: 22 Mar 201024 Mar 2010
Conference number: 26


Workshop26th European Workshop on Computational Geometry (EuroCG 2010)
Abbreviated titleEuroCG 2010
Internet address


Dive into the research topics of 'Approximation algorithms for free-label maximization'. Together they form a unique fingerprint.

Cite this