Computing the visibility polygon of an island in a polygonal domain (Q513290)

This paper focuses on the problem of computing the (weak) visibility polygon from a polygonal obstacle \(P^*\) (an island) in a given set \(P\) comprising \(n\) vertices and \(h\) pairwise disjoint obstacles. The authors show that the complexity of previously proposed algorithms, \(O(n^4)\), can be improved as a function of \(h\) and present an algorithm of complexity \(O(n^2h^2)\) when \(h=o(n).\) Moreover, when all obstacles are convex, the complexity is reduced to \(O(n+h^4)\). The paper commences with an overview of the problem and the introduction of preliminary concepts such as the corridor structure, bays and canals. The SO algorithm is also briefly presented. Next, the authors describe their novel approach, focusing on three types of edges and the illumination gates and their role in computing \(\mathrm{Vis}(P^*)\). The paper concludes with the description of the new algorithm applied to the convex version of the problem, i.e., all obstacles in \(P\) are convex polygons, which focuses on generating pseudo-triangles and using them to compute the union \(\mathrm{Vis}(P^*)\).