0

Assuming euclidean distance, how I can I find things nearby to a set of starts for a bunch of objects?

The best I can think of is n2 log n (running Dijkstra for each individual thing), which seems incredibly slow and problematic for what I'm trying to do. This problem, for context, is that I have these objects in a DB, and I need to load what is nearby on a semi-often basis. I abstracted the problem away to the following problem.

input: 
    possibleStarts: [(2,3), (5,7), (7,9)]
    possibleObjects: [(5,4),(1,3), (7,8), (1,4) ]
output:
{
       (2,3): [(1,3), (1,4), (5,4), (7,8)],
       (5,7): [(5,4), (7,8), (1,4), (1,3)],
       (7,9): [(7,8), (5,4), (1,4), (1,3)]
}

if at all applicable, I am using Firestore

Ronak Shah
  • 936
  • 9
  • 17
  • I was looking into pre-sorted / indexing my possibleObjects array somehow, but how can you optimize sorting if you never know where the start is? – Ronak Shah Jul 26 '20 at 08:12
  • 1
    It's a big area of knowledge that has no easy answer, since it depends on how much you're prepared to code, exactly what your DB can do, and the details of your how your objects are distributed and the exact sorts of queries you want. It could be as easy as creating region buckets (and a search would be restricted to a few buckets), but it's hard to say. Maybe look at: https://blog.mapbox.com/a-dive-into-spatial-search-algorithms-ebd0c5e39d2a – Paul Hankin Jul 26 '20 at 08:42
  • Running geoqueries on Firestore is usually done using geohashes (or a similar algorithm like S2). See my talk on the subject: https://www.youtube.com/watch?v=mx1mMdHBi5Q and some of the previous questions on the topic: https://stackoverflow.com/search?q=%5Bgoogle-cloud-firestore%5D+nearby – Frank van Puffelen Jul 26 '20 at 15:26

0 Answers0