1

Suppose you are given a hand drawn constellation (2d distribution of points) and a map of all stars, and are asked to find an actual star distribution sufficiently similar (with Kolmogorov Smirnov <= some_threshold) to the hand drawn constellation, if one exists.

Is there a classical algorithm for this kind of approximate distribution search?

Else do others have insights on how to reduce the complexity of this problem? I continue to be stumped by the fact that the user's hand-drawn constellation has no notion of scale or rotation...

Spektre
  • 49,595
  • 11
  • 110
  • 380
duhaime
  • 25,611
  • 17
  • 169
  • 224
  • 1
    Are there lines drawn between the stars you’re given? Or are they just a 2D point cloud? – templatetypedef Jun 10 '22 at 15:27
  • If you see a good shortcut that uses lines between the hand-drawn constellation, I'm eager to hear what you have in mind! – duhaime Jun 10 '22 at 15:32
  • So to clarify: you’re given a reference set of all the stars in the sky, and you’re also given a second set of points, and the goal is to figure out which set of stars best match those points? – templatetypedef Jun 10 '22 at 15:37
  • Try drawing the Big Dipper by hand without having recently looked at an image of the Big Dipper, and you'll understand the impossibility of this task. The hand drawn image won't match the star map in any significant way. The only way this works is if there's a limited number of very simple constellations to choose from. – user3386109 Jun 10 '22 at 17:27
  • @templatetypedef essentially yes, though we don't need the global optimum match--the first sufficiently similar match is good enough – duhaime Jun 10 '22 at 18:01
  • 1. I think this is called **pattern matching** instead of distribution matching ... 2. there are many possible approaches for this for starters see [Is it possible to make a correlation between an image and a constellation?](https://stackoverflow.com/a/28958816/2521214) and [How to compare two shapes?](https://stackoverflow.com/a/22166032/2521214) To fish inside a big pool like [BSC](http://tdc-www.harvard.edu/catalogs/bsc5.html) you can enhance speed with RANSAC ... if you use huge catalog (like Hipparcos,Tycho ...) then speed up is a must however I see no point on not using BSC for this. – Spektre Jun 11 '22 at 05:41
  • I retagged your question (check it and repair if I mess it up) beware "distribution" implies probabilistic (stochastic) problems which is not your case ... I would change the title as right now is misleading a lot ... for example something like `constellation matching in 2D` ... however such major change in title is better to do for the author itself ... – Spektre Jun 11 '22 at 05:48

0 Answers0