A Voronoi diagram is a basic geometric structure that partitions the space into regions associated with a given set of sites, such that all points in a region are closer to the corresponding site than to all other sites. While being thoroughly studied in Euclidean space, they are also of interest in hyperbolic space. In fact, there are several algorithms for computing hyperbolic Voronoi diagrams that work with the various models used to describe hyperbolic geometry. However, the polar-coordinate model has not been considered before, despite its increased popularity in the network science community. While Voronoi diagrams have the potential to advance this field, the model is geometrically not as approachable as other models, which impedes the development of geometric algorithms. In this paper, we present an algorithm for computing Voronoi diagrams natively in the polar-coordinate model of the hyperbolic plane. The approach is based on Fortune's sweep line algorithm for Euclidean Voronoi diagrams. We characterize the hyperbolic counterparts of the concepts it utilizes, introduce adaptations necessary to account for the differences, and prove that the resulting algorithm correctly computes the Voronoi diagram in time $O(n \log(n))$.


翻译:沃罗诺伊图是一种基本的几何结构,它将空间分割成与一组特定站点相关的区域,因此,一个区域的所有点都比其他站点更接近相应站点。 在欧几里德空间进行彻底研究的同时, 它们也关心双曲空间。 事实上, 有几种计算双曲伏罗诺伊图的算法, 与用来描述双曲几何的各种模型一起工作。 然而, 尽管极地相坐标模型在网络科学界越来越受欢迎, 但它以前从未被考虑过。 虽然沃罗诺伊图具有推进这个域的潜力, 但该模型的几何学角度无法像其他模型那样接近, 从而阻碍了几何算算算算法的发展。 在本文中, 我们提出一种计算沃罗诺伊图的算法, 以用于描述超偏差几度的模型为主。 这种方法以福图的扫描线算法为基础, 我们描述它所使用的概念的双向对等方, 引入必要的调整, 以计算美元为时值的模型, 并证明Voronalog 的算法正确计算结果。

0
下载
关闭预览

相关内容

ACM/IEEE第23届模型驱动工程语言和系统国际会议,是模型驱动软件和系统工程的首要会议系列,由ACM-SIGSOFT和IEEE-TCSE支持组织。自1998年以来,模型涵盖了建模的各个方面,从语言和方法到工具和应用程序。模特的参加者来自不同的背景,包括研究人员、学者、工程师和工业专业人士。MODELS 2019是一个论坛,参与者可以围绕建模和模型驱动的软件和系统交流前沿研究成果和创新实践经验。今年的版本将为建模社区提供进一步推进建模基础的机会,并在网络物理系统、嵌入式系统、社会技术系统、云计算、大数据、机器学习、安全、开源等新兴领域提出建模的创新应用以及可持续性。 官网链接:http://www.modelsconference.org/
【硬核书】矩阵代数基础,248页pdf
专知会员服务
86+阅读 · 2021年12月9日
专知会员服务
77+阅读 · 2021年3月16日
最新《图神经网络知识图谱补全》综述论文
专知会员服务
157+阅读 · 2020年7月29日
【新书】Python编程基础,669页pdf
专知会员服务
196+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Arxiv
0+阅读 · 2022年2月13日
Hyperbolic Graph Attention Network
Arxiv
6+阅读 · 2019年12月6日
VIP会员
Top
微信扫码咨询专知VIP会员