Labeling Subway Lines
Labeling Subway Lines
复制标题
标记地铁线路
DOI：
10.1007/3-540-45678-3_55
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Wolff
中科院分区：
文献类型：
--
作者：
Maria Angeles Garrido;C. Iturriaga;A. Márquez;J. Portillo;Pedro Reyes;A. Wolff
地图、海图、图表和图形图上的图形要素通常必须用文本标注来表达其含义。在本文中，我们专注于标记图式化的地图，例如，地铁网络时出现的问题。我们提出的算法标记点的轴平行的矩形标签的等高线。我们的目标是在所有点都必须被标记的约束下最大化标签大小，即使是一个看似强大的简化一般点标记问题，即决定一组点是否可以标记一条水平线上的滑动矩形标签，原来是弱NP完全的。这是已知属于此类的第一个标记问题。在斜线情况下，如果每个点有4个标记位置，则用最大正方形标记的时间为O（nlogn），如果标记可以滑动，则用最大正方形标记的时间为O（n3logn）。我们还研究了矩形标签。
Graphical features on map, charts, diagrams and graph drawings usually must be annotated with text labels in order to convey their meaning. In this paper we focus on a problem that arises when labeling schematized maps, e.g. for subway networks. We present algorithms for labeling points on a line with axis-parallel rectangular labels of equal height. Our aim is to maximize label size under the constraint that all points must be labeled.Even a seemingly strong simplification of the general point-labeling problem, namely to decide whether a set of points on a horizontal line can be labeled with sliding rectangular labels, turns out to be weakly NPcomplete. This is the first labeling problem that is known to belong to this class. We give a pseudo-polynomial time algorithm for it.In case of a sloping line points can be labeled with maximum-size square labels inO(n log n)time if four label positions per point are allowed and inO(n3log n)time if labels can slide. We also investigate rectangular labels.