CODEWITHSUNDEEP
algorithmgraph
ludo
ludo

Reputation: 1466

Finding points with minimum connectivity distance from room

I am implementing an algorithm to find the minimum spanning corridor in a set of rooms. Currently I have the algorithm figured out, I am just trying to implement it. Part of it involves finding so called "special points" of a given room. A "special point" of a rectangle, is a point that has the minimum distance to the farthest point of another rectangle. For example:enter image description here

The special point for room R1 would be v6 or v7, as both have the same minimum distance to the farthest point in a rectangle other than R1. Likewise the special point for rectangle R8 is v13 or v14, as both have the same minimum distance to the farthest point in a rectangle other than R8. Currently I have the points represented in adjacency lists, with every adjacent point in the list. Moreover I have every room in adjacency lists with each of its boundary points as values. I also have every point with every room that it belongs to.

Currently I am calculating the special point by looking at the distance to the farthest point in every rectangle around that point. Although that is fast, it clearly fails in the following example: enter image description here

As my current implementation will identify V1 and V2 as a tie for the special point of R9, when clearly V2 is the special point (as the distance from V2 to the farthest point in R3 is clearly smaller than the distance from V1 to the farthest point in R2). I could implement it by calculating the distance to the farthest point of all rectangles in the graph and picking the minimum, however I feel that there is a more efficient way of doing so. My thoughts are around some way of sorting the rooms and only checking some rooms, however I still don't have a full algorithm. Any ideas?

Thanks in advance.

Upvotes: 4

Views: 677

Answers (2)

TooTone
TooTone

Reputation: 8126

In summary, I suggest running Dijkstra's algorithm from all points on your source rectangle simultaneously, with a modified stopping condition. The algorithm keeps track of the current lowest special distance found so far during the search, and doesn't search any further for points that are already further away than the current lowest special distance so far. Some pseudocode below, which uses a dictionary to store target point => (best distance, source point) mappings.

enqueue all points on source rectangle
special distance = infinity
while (queue not empty) {
    point = dequeue
    if (distance to point < best distance found to point AND 
        distance to point < special distance) {
        best distance found to point = distance to point
        rect = rectangle of point
        if (all points found in rect) {
            special distance to this rect = max(distances found to this rect)
            if (special distance to this rect < special distance) {
                special distance = special distance to this rect
            }
        } 
    }
}

Motivating details below:

You could run Dijkstra's algorithm to find all points from each source point on the source rectangle to a set of target points. Essentially Dijkstra's algorithm is breadth first search where you only search further from the point at the head of the queue if it meets the condition that it is the shortest path found to that point from your source point.

If you used this condition, you would find the shortest path to all points. You could then compute the longest distance for each target rectangle, and take the minimum of these -- the "special distance" for that source point (and then rerun for every point on the source rectangle and find the lowest special distance). However this is too much work as you will include a lot of points in your search that are far away from your source point and which you don't need to consider.

What you can do is maintain the current lowest special distance found during the run of the algorithm, by spotting when you've found all points for a rectangle and updating the current lowest special distance accordingly (it starts off at some high number like INT_MAX in C). You then augment the condition for taking points forward by saying that their distance from the source point also has to be less than the current lowest special distance (clearly if the current point is further than the current lowest special distance then you can't do any better by considering paths that lead from it.)

If you are going to be finding special points for every rectangle, you might want to consider running the Floyd–Warshall algorithm, which will compute the shortest distance between every pair of points.

Upvotes: 2

Apiwat Chantawibul
Apiwat Chantawibul

Reputation: 1463

This is not a full answer. It is meant to confirm/formulate the definition of "special points".

Quote from OP:

A "special point" of a rectangle, is a point that has the minimum distance to the farthest point of another rectangle.

Here is my understanding. The special point v* of room r is given by:

enter image description here

Where

  • V_r is the set of vertices around room r
  • R is the set of all rooms
  • D(v,v') is the distance between two given vertices

So, one can see that:

  • destination vertex v' is chosen to be as far as possible from v
  • but v' has to be inside destination room r' which is chosen to minimize the distance

If I'm not too far off with this definition, then you should be able to brute-force search v*(r) with just 3 nested loops.

Of course, you are interested in more efficient method. However, let just make sure I understand "special points" correctly first.

Upvotes: 1

Related Questions