OfflineReverseGeocode VS timezones-api

A kd-tree is the generalized data structure that can do log(n) lookups of nearest in any dimensions. I wrote an implementation for nearest to a geographical point years ago (since ported to many other languages): https://github.com/AReallyGoodName/OfflineReverseGeocode

A less generalized solution is to grid things up (quad tree and bsp trees) as you implied above but the kd-tree is the generalized solution without edge cases (what if the majority of points of interest end up in a single grid square in your example?). A kd-tree is essentially what a sort list is for one dimensional data but instead supports multiple dimensions.

I wrote a tutorial on SpatiaLite here: https://datasette.io/tutorials/spatialite - "Building a location to time zone API with SpatiaLite"

It shows how to use SpatiaLite + Datasette to build an API that can tell you what timezone a latitude/longitude point is in, using data derived from OpenStreetMap via https://github.com/evansiroky/timezone-boundary-builder

Here's a demo: https://timezones.datasette.io/timezones/by_point?longitude=... - add ".json" to the URL for the JSON output.

It had been quite a while since a major release, but then SpatiaLite 5.0 came out a couple of months ago with some very significant new features - the K-Nearest-Neighbor stuff is particularly interesting. https://www.gaia-gis.it/fossil/libspatialite/wiki?name=5.0.0...

I've built a few fun demos using SpatiaLite and Datasette. Here's an API that tells you the timezone for a latitude longitude point:

https://timezones-api.datasette.io/timezones/by_point?longit... - implementation here: https://github.com/simonw/timezones-api

And here's the same thing for which US county a point is within: https://us-counties.datasette.io/counties/county_for_latitud... - implementation here: https://github.com/simonw/us-counties-datasette

I've also built an experimental Datasette plugin that lets you draw a shape on a Leaflet map to generate a GeoJSON polygon, then uses SpatiaLite to show you geometries that are contained by that drawn polygon. I wrote about that here: https://simonwillison.net/2021/Jan/24/drawing-shapes-spatial...