Finding the cleanest empty direct path through multiple points

Question

I create a simple game and come up with this problem when developing AI for my game: Given a set of N points inside a rectangle in a Cartesian coordinate, I need to find the widest direct path through this rectangle. The path must be empty (i.e. do not contain any point).

I wonder if there is an effective algorithm to solve this problem? Can you suggest any keyword / document / everything related to this problem?

EDIT: A rectangle is always defined by four dots in the corner. I have added an image for illustration. the path in the above images is indicated by two red lines

Answer 1

This is the widest problem with an empty corridor. Houle and Maciel gave O (n ² ) - time, an O (n) -space algorithm in a 1988 technical report entitled "Finding the Cleanest Empty Corridor Through Many Points" that does not seem to be available online. Fortunately, Janardan and Prepata describe this algorithm in Section 4 of their article Problems with the largest corridor that is available.

Answer 2

Scroll through all pairs of points. Draw line l through the pair. (^ 1) On each side l either there are other points or not. If not, then there is no way on this side l. If there are other points, scroll through the points calculating the perpendicular distance d from l to each such point. Record the minimum d. This is the widest path on the other side of l. Continue the cycle through all the pairs, comparing the widest path for this pair with the previous widest path.

This algorithm can be considered naive and works in O(n^3) time.

Edit: The above algorithm skips the case. Insert ^ 1 above: "Draw two lines perpendicular to l through each point of the pair. If there is no third point between the lines, then write down the distance d between the points. This makes up the path." Continue the algorithm to ^ 1. With an additional case, the algorithm is still O(n^3)

Answer 3

Myself, I would start by looking at the Delaney triangulation of a set of points: http://en.wikipedia.org/wiki/Delaunay_triangulation

There are apparently a lot of resources for efficient algorithms to build this here - the Fortune algorithm in O (n log n) for starters.

My intuition tells me that your widest path will be determined by one of the edges on this graph (namely, it will work perpendicular to the edge, and its width will be equal to the length of the edge). How to sort ribs, check candidates and identify the widest path. I like this question and I will continue to think about it. :)

EDIT 1: My intuition does not allow me! A simple equilateral triangle is a counter example: the widest path is shorter than any of the edges of the triangulation. Still thinking ...

EDIT 2: So, we need a black box algorithm that, given the two points in the set, finds the widest path through the set of points, which is limited to these two points. (Visualize two parallel lines passing through two points, rotate them in harmony with each other until there are no points between them). Let me call the runtime of this algorithm "R".

With this algorithm, we can do the following:

• Build a Delaunay triangulation of a set of points: O (n log n)
• Sort edges by width: O (n log n)
• Starting at the largest edge and moving down, use the black box algorithm to determine the widest path that includes these two points; saving it as X: O (nR))
• Stop if the investigated edge is shorter than the width of X.

Steps 1 and 2 are good, but O (nR) is intimidating. If R turns out to be O (n), then already O (n ^ 2) for the whole algorithm. The best part is that for the general set of random points, we expect that we do not have to go through all the edges.