2020-02-12

Hot Topic

Dr. Martin Skrodzki, who stays at RIKEN iTHEMS as a postdoctoral researcher for the year 2020, gave a talk at the Math Seminar on February 7, 2020. The title of his talk was "Solved and open problems regarding the neighborhood grid data structure". He began with introducing the k-d tree for a finite set with coordinates in the plane and explained that by using this tree one can find the nearest point from a given point in a reasonable time. Then, he looked at the neighborhood grid data structure introduced by Joselli et al. in 2009, which is an n times n matrix filled by pairs of numbers (f(i,j),g(i,j)) where f and g are surjections to the set of numbers from 1 to n squared. He gave the definition of a stable state and explained that any grid data structure can be stabilized and that stabilization can be done in a short time using parallel computation. He explained the correspondence between a generic set of n squared points in the plane and stable grid data structures, and discussed several open questions around this correspondence. The talk was very accessible for everyone and the participants enjoyed it very much.