Given an isothetic polygon (sides parallel to the x-axis or y-axis) and 2 points (start and end) on the boundary of the polygon,
find the shortest path traveling only in the direction of the x or y axis (up, right, down, left), such that the entire polygon is visible by the time a point travels from the
start point to the
Does anyone know of an algorithm that solves the above problem statement? No requirements on running time as such.
The best I could come up with was probably:-
- Triangulate the polygon
- 3-color each vertex of the triangles such that no two vertices on an edge have the same color
- Choose the color with the minimum count, and then join them to form the path
But this does not form the path which is given in the question. Moreover, it is a heuristic, which is not really what is required.