Solved and open problems regarding the neighborhood grid data structure
 Date
 February 7 (Fri) at 16:00  18:10, 2020 (JST)
 Speaker

 Martin Skrodzki (Visiting Scientist, iTHEMS / Fellow, German Academic Scholarship Foundation, Germany)
 Venue
 Language
 English
February 7 at 16:0017:00 17:1018:10, 2020
In 2009, Joselli et al. introduced the neighborhood grid data structure for fast computation of neighborhood estimates for point clouds in arbitrary dimensions. Even though the data structure has been used in several applications and was shown to be practically relevant, it is theoretically not yet well understood even in the twodimensional case. The purpose of this talk is to present the data structure, give a timeoptimal building algorithm, and motivate several associated questions from enumerative combinatorics as well as lowdimensional (probabilistic) geometry. In case of questions that have been solved in the past, corresponding proofs will be provided. For the open question, the talk will list them as an outlook to possible future collaboration.