Using an approximate nearest neighbors search for this is just worse though.

You can retrieve the exact information even faster. From an (x,y,t) coordinate, you can find the exact index in constant time