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.
The different versions of the original document can be found in:
DOIS: 10.1016/j.comgeo.2011.10.004 10.1007/978-3-642-13731-0_28
Are you one of the authors of this document?