離散数理モデリングセミナー

過去の記録 ~09/25次回の予定今後の予定 09/26~

担当者 時弘哲治, ウィロックス ラルフ

2020年06月24日(水)

15:00-16:30   オンライン開催
Zoom を用いてオンラインで行います.参加希望の方はウィロックスまでZoomのリンクをお尋ねください.
Martin Skrodzki 氏 (RIKEN iTHEMS)
Combinatorial and Asymptotical Results on the Neighborhood Grid Data Structure (English)
[ 講演概要 ]
In 2009, Joselli et al. introduced the Neighborhood Grid data structure for fast computation of neighborhood estimates in point clouds. Even though the data structure has been used in several applications and shown to be practically relevant, it is theoretically not yet well understood. The purpose of this talk is to present a polynomial-time algorithm to build the data structure. Furthermore, we establish the presented algorithm to be time-optimal. This investigations leads to several combinatorial questions for which partial results are given.