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.