Skip to main content
3 of 3
deleted 34 characters in body
Casebash
  • 386
  • 4
  • 12

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.
Casebash
  • 386
  • 4
  • 12