Optimal labeling of point features in rectangular labeling models

摘要

We investigate the NP–hard label number maximization problem (LNM): Given a set of rectangular labels Λ, each of which belongs to a point feature in the plane, the task is to find a labeling for a largest subset Λ P of Λ. A labeling is a placement such that none of the labels overlap and each λΛ P is placed according to a labeling model: In the discrete models, the label must be placed so that the labeled point coincides with an element of a predefined subset of corners of the rectangular label, in the continuous or slider models, the point must lie on a subset of boundaries of the label. Obviously, the slider models allow a continuous movement of a label around its point feature, leading to a significantly higher number of labels that can be placed.