Discrete mathematical modelling seminar

Seminar information archive ~02/26Next seminarFuture seminars 02/27~

Organizer(s) Tetsuji Tokihiro, Ralph Willox


15:00-16:30   Online
The seminar will be held using Zoom. If you wish to participate, please contact R. Willox by email.
Martin Skrodzki (RIKEN iTHEMS)
Combinatorial and Asymptotical Results on the Neighborhood Grid Data Structure (English)
[ Abstract ]
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.