Search for points with a minimum distance from the room

Question

I am implementing an algorithm to find the minimum core corridor in a set of rooms. I have currently defined an algorithm, I'm just trying to implement it. Part of it includes the search for the so-called "special points" of a given room. A “singular point” of a rectangle is a point that has a minimum distance from the farthest point of another rectangle. For instance:

The special point for room R1 will be v6 or v7, since both have the same minimum distance to the farthest point in the rectangle other than R1. Similarly, the singular point for the rectangle R8 is v13 or v14, since both have the same minimum distance to the farthest point in the rectangle other than R8. Currently, I have points represented in adjacency lists, with each adjacent point in the list. In addition, I have each room in adjacency lists with each of its boundary points as values. I also have every point with every room to which it belongs.

I am currently calculating a special moment by considering the distance to the farthest point in each rectangle around this point. Although this is fast, in the following example it clearly does not work:

How my current implementation will identify V1 and V2 as a reference for the special point R9, when it is clear that V2 is a special point (since the distance from V2 to the most distant point in R3 is clearly less 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 the rectangles on the chart and choosing a minimum, however, I believe that there is a more efficient way to do this. My thoughts are about some way of sorting rooms and checking only some rooms, however I still do not have a complete algorithm. Any ideas?

Thanks in advance.

Answer 1

In conclusion, I suggest starting the Dijkstra's algorithm from all points on your original rectangle at the same time as the modified stop condition. The algorithm keeps track of the current low special distance found so far during the search, and does not look for further points that are already farther than the current low special distance. Below is the pseudo code that uses a dictionary to store target point mappings => (best distance, starting point).

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 } } } } 

Motivation below:

You can run the Dijkstra algorithm to find all the points from each source point in the source rectangle before the set of target points. In fact, Dijkstra’s algorithm is the first width search in which you are just starting to search further from a point at the beginning of the queue if it matches the condition that it is the shortest path found for this point from the starting point.

If you used this condition, you will find the shortest path to all points. Then you can calculate the longest distance for each target rectangle and take the minimum of them - the “special distance” for this starting point (and then repeat for each point of the original rectangle and find the lowest special distance). However, this is too much work, since you will include many points in your search that are far from your starting point and which you do not need to consider.

What you can do is maintain the current low special distance detected during the start of the algorithm by determining when you found all the points for the rectangle and accordingly update the current low special distance (it starts with some big number like INT_MAX in C). Then you increase the condition in order to take the points forward, saying that their distance from the starting point should also be less than the current minimum special distance (it is clear if the current point is greater than the current low special distance, then you can’t better by considering the paths leading from him.)

If you are going to find special points for each rectangle, you may need to run the Floyd-Warshall algorithm , which will calculate the shortest distance between each pair of points.

Answer 2

This is not a complete answer. It is intended to confirm / formulate the definition of "singular points".

Quote from OP:

A "singular point" of a rectangle is a point that has a minimum distance from the farthest point of another rectangle.

Here is my understanding. The singular point v* room r is defined as follows:

Where

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

So, you can see that:

• The final vertex v' selected as far as possible from v
• but v' must be inside the destination room r' , which is chosen to minimize the distance

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

Of course, you are interested in a more efficient method. However, let me just make sure that I first understand the "singular points" correctly.