Complex search algorithm - Points on a sphere - Best approach

Question

I have a very complex search problem which I can't wrap my head around:

While reading please remember I'm not asking for a specific solution! Only a general approach how such a problem can be solved and what kinds of algorithms to use (more below)

I have a sphere with around 120 000 weighted and named points mapped on its surface.

Now I take a section out of the sphere with somewhat around 10 of the highest weights (not guaranteed the 10 hightest weights!)

The Problem: I want to find the spot where the section was taken out, so that i could assign each point the "name" it would have had on the sphere

---

Characteristics of the points on the sphere.:

• 120 000
• The coordinates are exact
• The points are weighted

---

Characteristics of the points in the sector:

• The points are also weighted. The proportions are roughly the same as on the sphere, unfortunately I don't know a single inital weight. So my only chance is to compare the proportions.

• Not every point which is on the sphere is also visible in the section (sometimes only 5-10%). However the weigths matter:

  • The hightest weighted points do always appear.

  • The first non-visible points have guaranteed less weight than most of the visible points.

• The section could be rotated

• All points are a bit offset (not by much), but they aren't exactly on the spot where they were on the sphere

• Other errors could be possible too (like counting 2 points only once)

  ---

Additional info which might make the problem simpler:

• The sector is only around 1°x1° to 5°x5°. So maybe i could use a flat map instead of a sphere. (Just like Google Maps if you zoom out enougth

• The first non-visible points have guaranteed less weight than most of the visible points.

---

What I'm asking for:

What is the general approach to solve this problem? Are there any algorithms you might now on which I can orientate myself?

Anything between pure brute-force and AI is welcome!

---

Example image of a sector region which is detected by my algorithm: (A larger red rectangle = higher weight)

---

^{If you think this is a good question please consider upvoting to draw attention.}

Answer 1

Let me start by suggesting a brute-force method, then suggest some ways to speed it up:

Pick a pair of (high-weight) points $P_0,P_1$ in the sector. For each pair of points $Q_0,Q_1$ on the sphere, guess that maybe $P_0=Q_0$ and $P_1=Q_1$: align the sector (rotate & translate it) so that $P_0$ is on top of $Q_0$ and $P_1$ is on top of $Q_1$. There is a unique way to do this. Then check your candidate placement of the sector, by mapping the sector onto the globe and looking at all the other points in the sector to see how well they match the points on the sphere. If you enumerate all pairs of points $Q_0,Q_1$ on the sphere, you're guaranteed to find the correct placement of the sector for at least one of them. So, this algorithm works, at the cost of being slow: it takes $O(n^2)$ time, where $n$ is the number of points on the sphere.

You can dramatically speed this up in several ways.

First, you can filter by the distance $d(P_0,P_1)$ between the two points. Instead of enumerating all points $Q_0,Q_1$, only enumerate pairs $Q_0,Q_1$ such that $d(Q_0,Q_1) \approx d(P_0,P_1)$. How do you do that? You enumerate all possibilities for $Q_0$, and for each such $Q_0$, enumerate all points $Q_1$ that are at distance approximately $d(P_0,P_1)$ from $Q_0$. The latter can be done using a data structure for nearest neighbor search. If you choose two points $P_0,P_1$ that are close to each other, probably there will be only a small number of points $Q_1$ at that distance from $Q_0$. So, heuristically, the running time might become much closer to $O(n)$.

Second, you might be able to filter using the weights. You could pick a pair of high-weight points $P_0,P_1$ in the sector, and only consider points $Q_0,Q_1$ whose weights are above some threshold. You'd have to experiment how to choose that threshold. Or, you could enumerate the points $Q_0$ in sorted order of the weight, highest weight first.

You can increase robustness to small errors in the location of the points in the sector by repeating the above multiple times for multiple different choices of $P_0,P_1$.

Answer 2

I think this sounds like a pretty fascinating question.

If you can simply normalize all the weights to be between 0 and 1, both on the initial sphere and in the segment, then you can get the weight values to be comparable.

If that does not work, one algorithm I would try would be using a weighted k-means clustering algorithm both on the initial sphere, and also on the segment which you receive. This algorithm is discussed somewhat in this paper:

On Initializations for the Minkowski Weighted K-Means

I would suggest performing k-means in a way that you have a proportional number of clusters in the rectangular segment as compared to the number of points.

10 clusters for 5000 points in the segment? 240 clusters for the large sphere.

Now, once we have the membership of each point in each segment, (i.e. which centroid each one belongs to) we take each point and redefine it as a proportion of either the average value of its segment, or of the maximum value in its segment.

This normalizes all of the weights in a way that preserves the local proportions. Then, you could compare your clusters inside the segment to the clusters and shapes in the whole sphere.

This should be more robust if the proportions are locally a lot more similar to the original proportions than they would be globally.

A third option could be to treat these like constellations, and use a constellation finding approach.