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
- 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.