Space Partitioning on Sphere

Hmm, why not use the same grid system that is used to represent Earth coordinates. In other words use spherical coordinates.

Spherical coordinates can easily be worked out from Cartesian coordinates as long as you know the radius and position of the sphere in question.

So you create the boundaries virtually by specifying [?, ?] extent of each grid cell, as you may be used to when working with normal grids.

Then you can calculate indices for the cells by coordinates, which is done as following:

int GetLocationIndex(const Vec2f &sphericalPoint) 
{ 
 Vec2f indices2D = sphericalPoint / extent; 
 return (unsigned int)(indices2D.x) + extent.x*(unsigned int)(indices2D.y); 
}

The x coordinates of the vectors, are Theta, and the y coordinates are Phi.

Note, i have not tried this, so it is only an approach that may work.
However good luck

Regions computed by uniformly subdividing spherical coordinates are not very balanced. The regions near the poles will be a lot smaller than regions at the equator. It is better to uniformly subdivide the cylindrical coordinates (so you consider the longitude and z).

One easy way would be starting with cube and normalize the vertex posistions to a sphere.

maybe icospheres is what you are looking for

http://en.wikipedia.org/wiki/Icosphere

In case you are still interested, a simple method for detecting points in a tessellated sphere is to detect the side of the plane formed by 2 sphere points and the sphere center. (dot product of the normal), and perform this for each side of a triangle to detect if a point is inside. You can also use the radial distance from the center of the sphere to divide the elevation of a point.

maybe icospheres is what you are looking for

http://en.wikipedia.org/wiki/Icosphere

Seconding icospheres. I'm using one for a "tiny planet" style procedural environment and have found it very easy to work with. Some semi-discrete things I've implemented with on it so far are various procedural generation techniques, global illumination baking with radiosity, and collision detection with the ground. At no point did the shape of the environment pose a great challenge, thanks to the simplicity & elegance of icospheres. Here's a screenshot.

Don't use a subdivided octahedron (I tried this initially). At first glance, they appear more "square" and therefore easy to work with, but they're not very balanced, creating greatly varying triangles at the leaves. Plus, icospheres can be squared up as needed. Study the common net of an icosahedron to find out how. I just use five rects (I call "pents") that sit above each regular grid of triangles.

You should take a look at Healpix if you want an equal-area division.