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 "reasonably nicely distributed".
• 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.

Reasonably nicely distributed 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.