1
$\begingroup$

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.
Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

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 "bins" are, as far as I can tell, a synonym for your "cells".

Are those COBE-inspired mappings adequate for you?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you heaps for your suggestions - they are all very interesting. I am working on other stuff atm, but these should be very useful should I ever need to revisit this problem. $\endgroup$
    – Casebash
    Commented Jul 1, 2010 at 23:54
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, I believe that that does have the required properties, I will work on proving it $\endgroup$
    – Casebash
    Commented Oct 30, 2009 at 12:09
  • 1
    $\begingroup$ Calculating what square a point belongs to will just involve drawing a line back to the center and intersecting the icosahedron. Estimating the minimum distance between a point and a cell should be possible using the reverse triangle inequality. It won't have too many points which are close and it wouldn't really look nice if the areas weren't almost equal $\endgroup$
    – Casebash
    Commented Oct 30, 2009 at 12:18
1
$\begingroup$

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?)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry, I thought I had removed all of the references to the word squares and replace it with cells. The word square is quite strongly associated in my mind with grid. $\endgroup$
    – Casebash
    Commented Oct 30, 2009 at 11:50
  • 1
    $\begingroup$ I did think briefly of combining them, but it was one of those ideas which I had, but didn't fully consider as much as I should. Thanks, I'll see if I can find any combination that has these properties. $\endgroup$
    – Casebash
    Commented Oct 30, 2009 at 11:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .