This problem can be solved if we can dynamically adjust our grid size such that whenever we have a grid with a lot of places we break it down to create smaller grids. A couple of challenges with this approach could be: 1) how to map these grids to locations and 2) how to find all the neighboring grids of a grid.
Why is it a challenge to map grids to locations? We know the coordinates of each location and the boundaries of each grid. With that, we know which location goes in which grid.