(Faster) Multi-Sided Boundary Labelling
share
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≤ k≤ 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^3log n) and O(n^5) to solve the 1-bend three-sided and four-sided boundary labelling problems, respectively.
READ FULL TEXT