I am trying to write a function to do this:
Given a number of points on, let's say, the cartesian graph (each point has a x and y value), create a non-directed graph such that each point on the cartesian graph becomes a node in our non-directed graph. There is a path between two nodes if the cartesian graph doesn't have a point who's x and y value is between the two node's x and y values.
Say for example, we have 3 points:
(0,0)
(1,1)
(2,2)
Then the function should create the non-directed graph which connects (0,0) to (1,1) and (1,1) to (2,2). Note that (0,0) and (2,2) aren't connected because (1,1)'s x and y value are between (0,0) and (2,2)'s x and y values.
Currently, what I have would run at what I believe is O(N^3) time (correct me if I'm wrong). What it would do is order the points by x value, check each combination of 2 points, and then check every other point (whose x value is between the two point's x value) to see if there is another point whose x and y values are between the 2 points we chose. If there is no such point, then we would then add an edge between these two points in our adjacency list.
Is there any way to reduce the time complexity?