Minimum Point-Overlap Labeling
Minimum Point-Overlap Labeling
复制标题
DOI：
10.1007/978-3-319-57586-5_28
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Yuya Higashikawa;K. Imai;Yusuke Matsumoto;Noriyoshi Sukegawa;Yusuke Yokosuka
中科院分区：
文献类型：
--
作者：
Yuya Higashikawa;K. Imai;Yusuke Matsumoto;Noriyoshi Sukegawa;Yusuke Yokosuka
在空中交通管制中，与每架飞机相关的信息需要始终显示为标签。受此应用的启发，de贝格和Gerrits（Comput. Geom.2012）提出了自由标签最大化问题，其目标是最大化无交叉标签的数量。在本文中，我们介绍了一个替代标记问题的空中交通管制，称为点重叠最小化。在这个问题中，我们关注平面上一点上重叠标签的数量，并最小化这些数量中的最大值。与自由标签最大化中的最大化可读标签的数量不同，我们在这里最小化使不可读标签可读所需的成本。我们为任意矩形标签提供了使用LP舍入的4-逼近算法，并为单位正方形标签提供了更快的组合8-逼近算法。
In the air-traffic control, the information related to each air-plane needs to be always displayed as the label. Motivated by this application, de Berg and Gerrits (Comput. Geom. 2012) presentedfree-label maximizationproblem, 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, calledpoint-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.