One-and-a-half-side Boundary Labeling
One-and-a-half-side Boundary Labeling
复制标题
一侧半边界标记
DOI：
10.1007/978-3-642-22616-8_30
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
H.-C.Yen
中科院分区：
文献类型：
--
作者：
C.-C.Lin;S.-H.Poon;S.Takahashi H.-Y.Wu.;H.-C.Yen
边界内标注是指将矩形地图上的每个点通过一个直线段或直线段连接到地图外的一个标注上。在各种类型的前导序列中，所谓的类型前导序列由三个部分组成（从位点到其相关标签），这三个部分与标签所连接的一侧正交，然后平行，然后正交。本文研究了所谓的1.5边边界标号，其中，除了直接连接到地图的右侧之外，类型-的领导者可以暂时路由到左侧，然后最终路由到右侧。事实证明，允许type-opleaders利用地图的左侧是有益的，因为它在某些情况下会产生更好的标记结果。为了更好地理解这种新版本的边界标记，我们从计算复杂性的角度研究了总引线长度最小化问题以及1.5边边界标记变体的弯曲最小化问题，这些问题由底层标签大小（均匀与非均匀）和端口类型（固定比率，固定位置与滑动）参数化。对于非均匀标签的情况，上述两个问题一般是棘手的。我们能够为这些棘手的问题设计伪多项式时间的解决方案，并确定不同标签的数量在整体复杂性中所扮演的角色。另一方面，如果标签的大小相同，这两个问题都可以在多项式时间内解决。我们还描述了利用左侧路由类型opleaders没有帮助的情况。
Inboundary labeling, each point site in a rectangular map is connected to a label outside the map by aleader, which may be a rectilinear or a straight-line segment. Among various types of leaders, the so-called type-opoleader consists of three segments (from the site to its associated label) that are orthogonal, then parallel, and then orthogonal to the side to which the label is attached. In this paper, we investigate the so-called1.5-side boundary labeling, in which, in addition to being connected to the right side of the map directly, type-opoleaders can be routed to the left side temporarily and then finally to the right side. It turns out that allowing type-opoleaders to utilize the left side of a map is beneficial in the sense that it produces a better labeling result in some cases. To understand this new version of boundary labeling better, we investigate from a computational complexity viewpoint thetotal leader length minimizationproblem as well as thebend minimizationproblem for variants of1.5-side boundary labeling, which are parameterized by the underlying label size (uniform vs. nonuniform) and port type (fixed-ratio, fixed-position, vs. sliding). For the case of nonuniform labels, the above two problems are intractable in general. We are able to devise pseudo-polynomial time solutions for such intractable problems, and also identify the role played by the number of distinct labels in the overall complexity. On the other hand, if labels are identical in size, both problems become solvable in polynomial time. We also characterize the cases for which utilizing the left side for routing type-opoleaders does not help.