I am looking for a way to partially "grid" the surface of a sphere to have certain nice properties which will be defined precisely below. 


* The areas should be "almost equal".
* It should be possible to calculate in constant time what grid cell any point belongs to (including the boundaries, see below)
* I want to ensure that no point has "too many grid cells that are close".
* I want a constant time lower bound approximation (or exact solution!) for determining minimum distance between any point and a cell


**Definition of what I mean by gridding**


* Each grid cell is an "area" on the sphere. We will assume it is a reasonably well behaved mathematical object - ie. the boundary does not self intersect, the length of the boundary is finite and the grid cells are closed. Does this have a proper mathematical name?
* We wish to cover an area C with grid cells. C consists of "almost all" the sphere, ie. all except for possibly a disc of unspecified size. We are allowed to cover more than just C.
* Each point on the surface of the sphere "belongs" to exactly one grid cell. If it is in the interior of a grid cell, then it "belongs" to that cell. If it is on a boundary, it "belongs" to exactly one of those cells. To clarify, "belonging" is a function from each point on C to the set of grid cells.


**Definition of "too many close grid cells"**


Suppose there are n grid cells. Let r be the radius of a disc with area 1/n of the total area of the sphere. I want only a few grid cells with lower bound approximation <=r from any point. To be precise, I would like this to be asymptotically less than sqrt(n), preferably constant.


**Distance between a cell and a point**
Defined as the minimum distance between a point and any point "belonging" in the cell.


**Almost equal areas**


I want there to be constants `0<e<1<f` so that the area of each grid square is `e/n<a<f/n`


**Observations**


* If I was trying to cover a square on a plane, then normal gridding would trivially solve this. I think that it might be possible if I could wrap a normal grid around a sphere or project it or something. I'm not really sure.
* Latitude and longitude grid lines will fail due to too many squares meeting at the poles.



Grid with nice mathematical properties
Unfortunately, the sphere is not a "developable surface". This fact has annoyed map-makers for more than a millennium.


I find your focus on "cells" fascinating.
Most people seem fixated on trying to get points on the globe to correspond with points on a flat image, and don't seem concerned about dividing it up into areas.
The simplest way to convert (lat,long) coordinates to standardized areas is the ["Natural Area Code"](http://en.wikipedia.org/wiki/Natural_Area_Code), but it has the same problems near the poles as latitude and longitude.


Your "too many close grid cells" and "Distance between a cell and a point" criteria reminds me of the "Thomson problem".
I suspect you're trying to rule-out map projections like the Gall–Peters projection that, while they do have nice "equal area" properties, end up having a hundred little squares at the top and bottom of the on the map projected to a hundred long, narrow pie-slices that all touch a pole of the globe.


Perhaps you could pick one of the known [solutions to the "Thomson problem"](http://en.wikipedia.org/wiki/Thomson_problem) to build a nice grid. Most of those solutions look similar to a geodesic sphere -- but there are a few exceptions.


Perhaps the most famous application for "almost equal" patches is the Cosmic Background Explorer (COBE), which has inspired several mappings:


* the [COBE sky cube](http://en.wikipedia.org/wiki/Quadrilateralized_spherical_cube) (quadrilateralized spherical cube) -- an [equal-area projection of the sphere onto a cube](http://www.progonos.com/furuti/MapProj/Normal/ProjPoly/projPoly2.html) -- the 6 large squares divide easily into a nice square grid.
* [An icosahedron-based method for pixelizing the celestial sphere](http://space.mit.edu/home/tegmark/icosahedron.html) -- an equal-area projection of the sphere onto an icosahedron -- the 20 large equilateral triangles divide easily into a nice equilateral triangle grid; or into a nice regular hexagonal grid.
* the HEALPix projection


The COBE "bins" are, as far as I can tell, a synonym for your "cells".


Are those COBE-inspired mappings adequate for you?


