专栏首页arxiv.org翻译专栏一种高效实用的多重加权Voronoi图计算算法及实现(CS CG)
原创

一种高效实用的多重加权Voronoi图计算算法及实现(CS CG)

本文提出了一种简单的波前方法来计算欧氏平面上点和直线段的多重加权Voronoi图。如果输入点可以假设为随机加权点,则使用所谓的叠加排列[Har-Peled&Raichel, Discrete Comput. Geom. 53:547-568, 2015]允许实现预期的运行时复杂性O(nlog4n),同时仍然保持方法的简单性。在CGAL的基础上,实现了加权点作为输入点的完整算法。实验评估结果表明,O(nlog2n)是运行时的一个实用界。该算法除了可以处理乘法权值外,还可以处理加法权值,它为解决这个问题的一维版本提供了一个真正简单的O(nlogn)解。

原文题目:An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams

原文:We present a simple wavefront-like approach for computing multiplicatively weighted Voronoi diagrams of points and straight-line segments in the Euclidean plane. If the input sites may be assumed to be randomly weighted points then the use of a so-called overlay arrangement [Har-Peled&Raichel, Discrete Comput. Geom. 53:547-568, 2015] allows to achieve an expected runtime complexity of O(nlog4n), while still maintaining the simplicity of our approach. We implemented the full algorithm for weighted points as input sites, based on CGAL. The results of an experimental evaluation of our implementation suggest O(nlog2n) as a practical bound on the runtime. Our algorithm can be extended to handle also additive weights in addition to multiplicative weights, and it yields a truly simple O(nlogn) solution for solving the one-dimensional version of this problem.

原文作者:Martin Held, Stefan de Lorenzo

原文地址:https://arxiv.org/abs/2006.14298

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 随机存取机器程序的程序代数(cs)

    本文提出了一种以随机存取机(RAM)指令为基本指令的指令序列的代数理论,以及指令序列在执行过程中产生的行为,以及这些行为与RAM存储器之间的相互作用。这一理论为...

    用户7454091
  • 动力学方程的保守半拉格朗日格式第一部分:重构(cs)

    在本文中,我们提出并分析一种重建技术,使一个人设计高阶保守半拉格朗日格式的动力学方程。所提出的重构可以通过对数值解的多项式重构取滑动平均来获得。给出了高阶保守重...

    用户7454091
  • 动态网络识别的激励和测量的最优分配(cs)

    中文摘要:本文正式地阐述和分析了动态网络识别中激励和测量的最佳分配问题。最好的选择是用最宜的实验来实现最准确的识别。精度是由参数估计的渐近协方差矩阵的轨迹来评估...

    用户7454091
  • 法兰克福拉丁词典:从形态扩展和词嵌入到符号图(CS CL)

    在本文中,我们介绍了法兰克福拉丁语词典(FLL),这是中世纪拉丁语的词汇资源,用于拉丁文本的词素化和词素化的后期编辑。我们描述了造词机的最新发展,并针对Capi...

    刘子蔚
  • md5算法原理一窥(其一)

        首先,需要了解的事,md5并不是传说中的加密算法,只是一种散列算法。其加密的算法并不是我们说所的那样固定不变,只是一种映射的关系。 所以解密MD5没有现...

    Gxjun
  • 调查计算语言文档双语方法中的语言影响(Computation and Language)

    对于濒危语言而言,数据收集活动必须能够应对很多数据源自口传而且生产副本费用高昂的挑战。因此,为了确保录音的可解释性,至少要将这些录音转译成使用广泛的语言版本。本...

    用户6868260
  • 【论文推荐】最新六篇行人再识别(ReID)相关论文—和谐注意力网络、时序残差学习、评估和基准、图像生成、三元组、对抗属性-图像

    【导读】专知内容组整理了最近六篇行人再识别(Person Re-Identification)相关文章,为大家进行介绍,欢迎查看! 1. Harmonious ...

    WZEARW
  • JavaFX文档翻译——TriangleMesh篇

    Defines a 3D triangle mesh that consists of its associated VertexFormat and a ...

    大闲人柴毛毛
  • POJ 2370 Democracy in danger(简单贪心)

    Democracy in danger Time Limit: 1000MS Memory Limit: 65536K Total Submis...

    Angel_Kitty
  • 法兰克福拉丁语词典:从形态扩展和单词嵌入到符号图(CS CL)

    在这篇文章中,我们介绍了法兰克福拉丁语词典 (FLL),这是一个中世纪拉丁语的词典资源,既用于拉丁语文本的词法化,也用于词法化后的编辑。我们描述了最近在词典编纂...

    刘持诚

扫码关注云+社区

领取腾讯云代金券