map - What are some efficient Geohash bounding box coverage algorithms? -

my requirement is:

given lat-lon bounding box, return set of geohashes such that:

• the number of geohashes in set should small (1 5 geohash
  rectangles) if possible.
• the coverage should closed input lat-lon bounding box possible. tolerance +/- 10%. ok under-cover and/or over-cover little bit.
• it should efficient , can carried out on mobile device

i interested in algorithm or conceptual approach. plan implement in java/obj-c android , ios if no open source implementation exists.

this java project on github https://github.com/davidmoten/geo has documented algorithm doing want. in particular works nicely @ limits of geohash region (namely @ poles , @ -180/180 longitude line).

keeping number of geohashes small (1 5) tolerance 10% won't fly i'm afraid. 5 geohashes many rectangles covered geohashes @ 600% of area of target rectangle. in fact example below getting within 10% of area requires 667 hashes!

here's table taken readme on geo project site:

as quick example, bounding box proportioned more less screen schenectady ny , hartford ct in usa @ corners:

here hash counts different hash lengths:

m size in square degrees of total hashed area , area of bounding box.

 length  numhashes m/a     1       1         1694    2       1         53      3       4         6.6     4       30        1.6     5       667       1.08    6       20227     1.02    

the algorithm used efficient , relevant code has no dependency on other artifacts won't problem deploy mobile device supporting java (like android).