2

I have a scenario where there are 2 regions and a set of points in both of them. There is no particular pattern amongst the points in each region (we can't consider them to be forming a convex polygon or such.)

I wish to find the shortest distance connecting a point in region 1 with a point in region 2.

Pictorially, the situation can be described as follows:

Region 1:

enter image description here

----------- SOME SPACE ---------------

Region 2:

enter image description here

I know I can use the Naive algorithm but it will be O(n^2) but I wish to know if there exists a faster approach. I feel I can sort the set of points by y coordinates and try to find distance in a particular order, but am unable to prove the correctness of such approach.

Thanks.

Naman Bhalla
  • 48
  • 7
  • How do you get to O(n^2) and what is n? I feel you have to be more specific. The runtime of Dijkstra is O(E log E + V) where E is the number of edges and V is the number of vertices. The naive approach would run a Dijkstra from each vertex in Region 2 (smaller region) and stop if a node in Region 1 is reached. Thus the runtime would be O(K * (E log E + V)) where K is the number of nodes in Region 2. – SaiBot Apr 20 '18 at 08:02
  • Are you asking about the shortest path through a graph, or the shortest Euclidean distance between nodes? What's the purpose of those ovals? – Sneftel Apr 20 '18 at 08:05
  • 3
    I think your diagram is confusing people. If you're only interested in the *distances between points*, which I believe you are, you should remove the black lines as they are irrelevant. @SaiBot I think O(n^2) comes if there are `n` points in both regions and we compute all the pairwise distances, then take the minimum – AakashM Apr 20 '18 at 08:51
  • 1
    @AakashM ah, I thought this is about graph distance. I guess the graphs in the regions were confusing me. – SaiBot Apr 20 '18 at 08:56
  • A relatively easy approach is to build the convex hulls of both sets, which will reduce their size, then brute force on the remaining ones. Not optimal, but easy if you have a 2D convex hull handy. –  Apr 20 '18 at 12:30
  • @SaiBot By n, I refer to total number of points in the regions. I guess there is confusion because of the interconnections between the points in each region. O(n^2) algorithm will compute the euclidean distance between each pair and output the shortest one. So, for every point in region 1, distance will be computed with each point in region 2. – Naman Bhalla Apr 21 '18 at 05:58
  • @AakashM Thanks. Yes. That was what I meant. – Naman Bhalla Apr 21 '18 at 05:59
  • @YvesDaoust Thanks. I also considered that approach but am unable to prove that it actually shall be correct always. Can't there be some cases when a point with shortest distance isn't actually on convex hull for one of the regions ? – Naman Bhalla Apr 21 '18 at 06:00
  • @NamanBhalla: if the two clouds are linearly separable, I don't think so. If they intertwine, of course the solution can be inside. –  Apr 21 '18 at 10:36
  • @NamanBhalla: on second thoughts, you are quite right, the solution is not necessarily a hull vertex. In the case of disjoint hulls, the points to be considered are those such that the convex hull outline crosses their Voronoi cell. This includes the hull vertices and a few more inside. –  Apr 23 '18 at 06:34
  • @YvesDaoust Exactly my thought. Thankyou – Naman Bhalla Apr 23 '18 at 08:14

0 Answers0