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.