...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Flip Distance to some Plane Configurations
【24h】

Flip Distance to some Plane Configurations

机译：翻转距离到某些平面配置

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study an old geometric optimization problem in the plane. Given a perfect matching M on a set of n points in the plane, we can transform it to a non-crossing perfect matching by a finite sequence of flip operations. The flip operation removes two crossing edges from M and adds two non-crossing edges. Let f(M) and F(M) denote the minimum and maximum lengths of a flip sequence on M, respectively. It has been proved by Bonnet and Miltzow (2016) that f(M)=O(n^2) and by van Leeuwen and Schoone (1980) that F(M)=O(n^3). We prove that f(M)=O(n Delta) where Delta is the spread of the point set, which is defined as the ratio between the longest and the shortest pairwise distances. This improves the previous bound for point sets with sublinear spread. For a matching M on n points in convex position we prove that f(M)=n/2-1 and F(M)={{n/2} choose 2}; these bounds are tight.Any bound on F(*) carries over to the bichromatic setting, while this is not necessarily true for f(*). Let M' be a bichromatic matching. The best known upper bound for f(M') is the same as for F(M'), which is essentially O(n^3). We prove that f(M')=slant n-2 for points in convex position, and f(M')= O(n^2) for semi-collinear points.The flip operation can also be defined on spanning trees. For a spanning tree T on a convex point set we show that f(T)=O(n log n).
机译：我们研究平面中的一个旧几何优化问题。给定平面上一组n个点上的完美匹配M，我们可以通过有限的翻转操作序列将其转换为非交叉完美匹配。翻转操作从M移除两个相交边缘，并添加两个非相交边缘。令f（M）和F（M）分别表示在M上的翻转序列的最小和最大长度。 Bonnet和Miltzow（2016）证明f（M）= O（n ^ 2），van Leeuwen和Schoone（1980）证明F（M）= O（n ^ 3）。我们证明f（M）= O（n Delta），其中Delta是点集的扩展，定义为最长和最短成对距离之间的比率。这改善了具有亚线性扩展的点集的先前边界。对于凸点上n个点上的匹配M，我们证明f（M）= n / 2-1和F（M）= {{n / 2}选择2};这些边界是紧密的。F（*）上的任何边界都会延续到双色设置，而f（*）不一定是正确的。令M'为双色匹配。 f（M'）的最著名上限与F（M'）的上限相同，本质上为O（n ^ 3）。我们证明f（M'）<=倾斜n-2表示凸位置上的点，f（M'）= O（n ^ 2）表示半共线点.flip操作也可以在生成树上定义。对于凸点集上的生成树T，我们表明f（T）= O（n log n）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号