In the air-traffic control, the information related to each airplane needs to be always displayed as the label. Motivated by this application, de Berg and Gerrits (Comput. Geom. 2012) presented free-label maximization problem, where the goal is to maximize the number of intersection-free labels. In this paper, we introduce an alternative labeling problem for the air-traffic control, called point-overlap minimization. In this problem, we focus on the number of overlapping labels at a point in the plane, and minimize the maximum among such numbers. Instead of maximizing the number of readable labels as in the free-label maximization, we here minimize the cost required for making unreadable labels readable. We provide a 4-approximation algorithm using LP rounding for arbitrary rectangular labels and a faster combinatorial 8-approximation algorithm for unit-square labels.
展开▼
