首页> 外文期刊>Algorithmica >Multi-sided Boundary Labeling
【24h】

Multi-sided Boundary Labeling

机译:多面边界标签

获取原文
获取原文并翻译 | 示例

摘要

In the Boundary Labeling problem, we are given a set of n points, referred to as sites, inside an axis-parallel rectangle R, and a set of n pairwise disjoint rectangular labels that are attached to R from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called leaders, with at most one bend. In this paper, we study the Multi-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of R (here a crossing-free solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.
机译:在边界标记问题中,我们在平行于轴的矩形R内获得了一组n个点(称为站点),并从外部将N个成对的不相交矩形标签连接到R上。任务是通过不相交的直线路径(称为引导线)将站点与标签连接起来,并且最多只能弯曲一次。在本文中,我们研究了多面边界标签问题,其中标签位于封闭矩形的至少两侧。我们提出了一种多项式时间算法,该算法可计算无交叉引线布局(如果存在)。到目前为止,仅在标签位于R的一侧或相对两侧(此处始终存在无交叉解决方案)的情况下才知道这种算法。标签可能会贴在相邻侧面上的情况更加困难。我们提出了有效的算法,用于测试标记所有站点的无交叉引线布局的存在,并最大程度地增加无交叉引线布局中标记站点的数量。对于带有相邻边的双面边界标签,我们进一步展示了如何在无交叉布局中最小化总引线长度。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号