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:00-17:00 17:10-18: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 two-dimensional case. The purpose of this talk is to present the data structure, give a time-optimal building algorithm, and motivate several associated questions from enumerative combinatorics as well as low-dimensional (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.
