Approximation algorithms for free-label maximization |
| |
Authors: | Mark de Berg Dirk HP Gerrits |
| |
Institution: | Department of Mathematics and Computing Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|