1
$\begingroup$

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

enter image description here


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)


enter image description here


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

$\endgroup$
  • $\begingroup$ Are the point-weights unique, or can there be multiple with the same value? $\endgroup$ – Teknophilia Mar 3 '18 at 14:39
  • 2
    $\begingroup$ I can feel your enthusiasm for the problem. It's probably going to be interesting topic. However, I think the problem description needs some more work: (1) you mentioned the goal is to put name on each point but never deliberate more what 'name' is and how its suitability for each point could be evaluated. (2) it is implicitly implied that section has specific shape described by two angles. I can guess what you mean but you should be more explicit. $\endgroup$ – Billiska Mar 3 '18 at 14:39
  • 2
    $\begingroup$ On a second read, is this just a picture search on a larger picture? (just that the geometry is spherical.) $\endgroup$ – Billiska Mar 3 '18 at 14:41
  • $\begingroup$ @Teknophilia there are points with the same weigth $\endgroup$ – Sebastian Schneider Mar 3 '18 at 14:56
  • $\begingroup$ @Billiska I dont think so because there might be parts on the sphere which aren't in the sector $\endgroup$ – Sebastian Schneider Mar 3 '18 at 14:58
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ thanks for this detailed answer, i'll try this method soon! $\endgroup$ – Sebastian Schneider Mar 4 '18 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.