Grid with nice mathematical properties 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.

 A: I don't really understand what you want but what about using a geodesic sphere? Then no more than 6 cells meet at any point.
A: 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", 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" 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 (quadrilateralized spherical cube) -- an equal-area projection of the sphere onto a cube -- the 6 large squares divide easily into a nice square grid.

*An icosahedron-based method for pixelizing the celestial sphere -- 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?
A: It's impossible to cover a sphere with a grid of squares.  This can be proved, for example, by using an Euler characteristic argument.  I don't fully understand all your terminology, but assuming you really just want a fine mesh on the sphere, I think you could just use longitude and latitude lines, and if you have problems with the poles being close to too many cells you can just combine some of them.  (Or do you have some conditions on how the cells meet at vertices?)
