Conceptually this is a depth-limited quad tree. Practically this is
implemented using a z-order curve and run-length encoding that in a
vector together with the corresponding timezone.

With the current settings the result is about 200kB, a maximum error
distance of about 300m and a surface coverage of 99.2% for yielding the
correct IANA timezone or 99.6% for yielding at least an equivalent
IANA timezone. Not too bad considering the timezone shapefile that is
the input for all this is 100+MB.

Lookup cost is minimal, a single binary search and no memory allocations.

The generation script is supposed to run inside QGIS with the IANA
timezone shapefile loaded. With the current parameters it should finish
within an hour on 8 cores.

Before being fully integrated this needs a few more measurements with
different parameters. Also still to be investigated is how this can
replace the about 74kB worth of timezone data in the airport and train
station databases.