Dynamic Voronoi Diagram for Moving Disks

Chanyoung Song; Jehyun Cha; Mokwon LeeDeok-Soo Kim

首页> 外文期刊>IEEE transactions on visualization and computer graphics >Dynamic Voronoi Diagram for Moving Disks

【24h】

Dynamic Voronoi Diagram for Moving Disks

机译：Dynamic Voronoi Diagram for Moving Disks

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

Voronoi diagrams are powerful for understanding spatial properties. However, few reports have been made for moving generators despite their important applications. We present a topology-oriented event-increment (TOI-E) algorithm for constructing a Voronoi diagram of moving circular disks in the plane over the time horizon &inline-formula&&tex-math notation="LaTeX"&$[0, t^{infty })$&/tex-math&&alternatives&&mml:math&&mml:mrow&&mml:mo&[&/mml:mo&&mml:mn&0&/mml:mn&&mml:mo&,&/mml:mo&&mml:msup&&mml:mi&t&/mml:mi&&mml:mi&∞&/mml:mi&&/mml:msup&&mml:mo&)&/mml:mo&&/mml:mrow&&/mml:math&&inline-graphic xlink:href="kim-ieq1-2959321.gif"/&&/alternatives&&/inline-formula&. The proposed TOI-E algorithm computes the event history of the Voronoi diagram over the entire time horizon in &inline-formula&&tex-math notation="LaTeX"&$O(k_F log n + k_C n log n)$&/tex-math&&alternatives&&mml:math&&mml:mrow&&mml:mi&O&/mml:mi&&mml:mo&(&/mml:mo&&mml:msub&&mml:mi&k&/mml:mi&&mml:mi&F&/mml:mi&&/mml:msub&&mml:mo form="prefix"&log&/mml:mo&&mml:mi&n&/mml:mi&&mml:mo&+&/mml:mo&&mml:msub&&mml:mi&k&/mml:mi&&mml:mi&C&/mml:mi&&/mml:msub&&mml:mi&n&/mml:mi&&mml:mo form="prefix"&log&/mml:mo&&mml:mi&n&/mml:mi&&mml:mo&)&/mml:mo&&/mml:mrow&&/mml:math&&inline-graphic xlink:href="kim-ieq2-2959321.gif"/&&/alternatives&&/inline-formula& time with &inline-formula&&tex-math notation="LaTeX"&$O(n log n)$&/tex-math&&alternatives&&mml:math&&mml:mrow&&mml:mi&O&/mml:mi&&mml:mo&(&/mml:mo&&mml:mi&n&/mml:mi&&mml:mo form="prefix"&log&/mml:mo&&mml:mi&n&/mml:mi&&mml:mo&)&/mml:mo&&/mml:mrow&&/mml:math&&inline-graphic xlink:href="kim-ieq3-2959321.gif"/&&/alternatives&&/inline-formula& preprocessing time and &inline-formula&&tex-math notation="LaTeX"&$O(n + k_F + k_C)$&/tex-math&&alternatives&&mml:math&&mml:mrow&&mml:mi&O&/mml:mi&&mml:mo&(&/mml:mo&&mml:mi&n&/mml:mi&&mml:mo&+&/mml:mo&&mml:msub&&mml:mi&k&/mml:mi&&mml:mi&F&/mml:mi&&/mml:msub&&mml:mo&+&/mml:mo&&mml:msub&&mml:mi&k&/mml:mi&&mml:mi&C&/mml:mi&&/mml:msub&&mml:mo&)&/mml:mo&&/mml:mrow&&/mml:math&&inline-graphic xlink:href="kim-ieq4-2959321.gif"/&&/alternatives&&/inline-formula& memory for &inline-formula&&tex-math notation="LaTeX"&$n$&/tex-math&&alternatives&&mml:math&am

著录项

来源
《IEEE transactions on visualization and computer graphics》 |2021年第6期|2923-2940|共18页
作者
Chanyoung Song; Jehyun Cha; Mokwon LeeDeok-Soo Kim;
展开▼
作者单位

School of Mechanical Engineering, Hanyang Univeristy, Seoul, South Korea;

Voronoi Diagram Research Center and HYU-HPSTAR-CIS Global High Pressure Research Center and School of Mechanical Engineering, Hanyang Univeristy, Seoul, South Korea;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类模式识别与装置;
关键词
Drones; Heuristic algorithms; Vehicle dynamics; Generators; Prediction algorithms; Probes; Collision avoidance; Unmanned vehicles; moving vehicles; path planning; collision avoidance; topology event; weighted Voronoi diagram;

Dynamic Voronoi Diagram for Moving Disks

摘要

著录项

相关主题

期刊订阅