3
$\begingroup$

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 end point. Polygon Example Path

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

  1. Triangulate the polygon
  2. 3-color each vertex of the triangles such that no two vertices on an edge have the same color
  3. 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.

$\endgroup$
4
  • $\begingroup$ Is the polygon simple (i.e. without holes)? Is the visibility axis-parallel as well: are all the points $w$ s.t. $vw$ lies in the polygon considered visible from $v$, or does $vw$ need to be axis-parallel? This paper provides an algorithm for the case of polygonal paths and where the endpoints of the path can be freely chosen by the algorithm. I don't see a way to directly apply the result to your case, but their approach is likely relevant. $\endgroup$
    – Discrete lizard
    Nov 30, 2023 at 9:21
  • $\begingroup$ The polygon is simple A point is visible from another point if you can draw a line between them (axis-parallel or not) without obstructing with boundary of the polygon. Thanks for the paper, it does seem useful $\endgroup$ Nov 30, 2023 at 10:09
  • $\begingroup$ this does not form the path which is given in the question In general, there should be many shortest paths. $\endgroup$
    – greybeard
    Dec 1, 2023 at 10:55
  • $\begingroup$ What I meant is that it does not form a path that is axis-parallel, it goes in angles from vertex to vertex. You are right, there might be many shortest paths. Any of those shortest paths (axis-parallel) will do. $\endgroup$ Dec 1, 2023 at 14:30

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.