论文标题
（更快）多边边界标签
(Faster) Multi-Sided Boundary Labelling
论文作者
论文摘要
1弯边界标签问题由轴线对准的矩形$ b $，$ n $点（称为站点）和内部的$ n $点（称为端口）组成，沿着$ b $的边界的标签上的$ n $点（称为端口）。目的是找到一组$ n $轴对准的曲线（称为领导者），每个曲线最多都有一个弯曲，并将一个站点连接到一个端口，以使领导者是成对的脱节。如果端口出现在$ b $的$ k $不同方面，则1弯边界标签问题是$ k $ side（$ 1 \ leq k \ leq 4 $）。 Kindermann等。 [“多面边界标签”，算法，76（1）：225-258，2016]表明，可以分别以$ O（n^4）$和$ O（n^9）$时间来解决1弯的三面和四面边界标签问题。 Bose等。 [SWAT，12：1-12：14，2018]通过将问题减少到计算OuterString图中的最大独立设置，将后者的运行时间提高到$ O（n^6）$。在本文中，我们通过提供具有运行时间$ O（n^3 \ log n）$和$ O（n^5）$的新算法来改善这两个结果，分别解决了1弯的三面和四面边界标签问题。
A 1-bend boundary labelling problem consists of an axis-aligned rectangle $B$, $n$ points (called sites) in the interior, and $n$ points (called ports) on the labels along the boundary of $B$. The goal is to find a set of $n$ axis-aligned curves (called leaders), each having at most one bend and connecting one site to one port, such that the leaders are pairwise disjoint. A 1-bend boundary labelling problem is $k$-sided ($1\leq k\leq 4$) if the ports appear on $k$ different sides of $B$. Kindermann et al. ["Multi-Sided Boundary Labeling", Algorithmica, 76(1): 225-258, 2016] showed that the 1-bend three-sided and four-sided boundary labelling problems can be solved in $O(n^4)$ and $O(n^9)$ time, respectively. Bose et al. [SWAT, 12:1-12:14, 2018] improved the latter running time to $O(n^6)$ by reducing the problem to computing maximum independent set in an outerstring graph. In this paper, we improve both previous results by giving new algorithms with running times $O(n^3\log n)$ and $O(n^5)$ to solve the 1-bend three-sided and four-sided boundary labelling problems, respectively.
