Location of highest density on a sphere

Question

I have a lot of points on the surface of the sphere. How can I calculate the area/spot of the sphere that has the largest point density? I need this to be done very fast. If this was a square for example I guess I could create a grid and then let the points vote which part of the grid is the best. I have tried with transforming the points to spherical coordinates and then do a grid, both this did not work well since points around north pole are close on the sphere but distant after the transform.

Thanks

Answer 1

You can use the Peters projection, which preserves the areas.

This will allow you to efficiently count the points in a grid, but also in a sliding window (box Parzen window) by using the integral image trick.

Answer 2

Consider using a geographic method to solve this. GIS tools, geography data types in SQL, etc. all handle curvature of a spheroid. You might have to find a coordinate system that uses a pure sphere instead of an earthlike spheroid if you are not actually modelling something on Earth.

For speed, if you have large numbers of points and want the densest location of them, a raster heatmap type solution might work well. You could create low resolution rasters, then zoom to areas of high density and create higher resolution only cells that you care about.

Answer 3

I am not master of mathematics but may be it can solve by analytical way as:

1.Short the coordinate

2.R=(Σ(n=0. n=max)(Σ(m=0. M=n)(1/A^diff_in_consecative))*angle)/Σangle

A=may any constant

Answer 4

There is in fact no real reason to partition the sphere into a regular non-overlapping mesh, try this:

• partition your sphere into semi-overlapping circles

  see here for generating uniformly distributed points (your circle centers)

  Dispersing n points uniformly on a sphere

• you can identify the points in each circle very fast by a simple dot product..it really doesn't matter if some points are double counted, the circle with the most points still represents the highest density

mathematica implementation

this takes 12 seconds to analyze 5000 points. (and took about 10 minutes to write )

 testcircles = { RandomReal[ {0, 1}, {3}] // Normalize};
 Do[While[ (test = RandomReal[ {-1, 1}, {3}] // Normalize ;
     Select[testcircles , #.test > .9 & , 1] ) == {} ];
        AppendTo[testcircles, test];, {2000}];
 vmax = testcircles[[First@
    Ordering[-Table[ 
        Count[ (testcircles[[i]].#) & /@ points   , x_ /; x > .98 ] ,
              {i, Length[testcircles]}], 1]]];

Answer 5

To add some other, alternative schemes to the mix: it's possible to define a number of (almost) regular grids on sphere-like geometries by refining an inscribed polyhedron.

The first option is called an icosahedral grid, which is a triangulation of the spherical surface. By joining the centres of the triangles about each vertex, you can also create a dual hexagonal grid based on the underlying triangulation:

Another option, if you dislike triangles (and/or hexagons) is the cubed-sphere grid, formed by subdividing the faces of an inscribed cube and projecting the result onto the spherical surface:

In either case, the important point is that the resulting grids are almost regular -- so to evaluate the region of highest density on the sphere you can simply perform a histogram-style analysis, counting the number of samples per grid cell.

As a number of commenters have pointed out, to account for the slight irregularity in the grid it's possible to normalise the histogram counts by dividing through by the area of each grid cell. The resulting density is then given as a "per unit area" measure. To calculate the area of each grid cell there are two options: (i) you could calculate the "flat" area of each cell, by assuming that the edges are straight lines -- such an approximation is probably pretty good when the grid is sufficiently dense, or (ii) you can calculate the "true" surface areas by evaluating the necessary surface integrals.

If you are interested in performing the requisite "point-in-cell" queries efficiently, one approach is to construct the grid as a quadtree -- starting with a coarse inscribed polyhedron and refining it's faces into a tree of sub-faces. To locate the enclosing cell you can simply traverse the tree from the root, which is typically an O(log(n)) operation.

You can get some additional information regarding these grid types here.

Answer 6

Treating points on a sphere as 3D points might not be so bad.

Try either:

1. Select k, do approximate k-NN search in 3D for each point in the data or selected point of interest, then weight the result by their distance to the query point. Complexity may vary for different approximate k-NN algorithms.
2. Build a space-partitioning data structure like k-d Tree, then do approximate (or exact) range counting query with a ball range centered at each point in the data or selected point of interest. Complexity is O(log(n) + epsilon^(-3)) or O(epsilon^(-3)*log(n)) for each approximate range query with state of the art algorithms, where epsilon is the range error threshold w.r.t. the size of the querying ball. For exact range query, the complexity is O(n^(2/3)) for each query.