Computing the visibility polygon of an island in a polygonal domain
type: Item
instance of: scholarly article
title: Computing the visibility polygon of an island in a polygonal domain
zbMATH Open document ID: 1364.68343
author: Danny Z. Chen
author: Haitao Wang
published in: Algorithmica
publication date: 2017-03-06T00:00:00Z
review text: 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^*)\).
reviewed by: Irina Ioana Mohorianu
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6691976
zbMATH Keywords: visibility polygons
zbMATH Keywords: polygonal domains
zbMATH Keywords: polygon with holes
zbMATH Keywords: algorithms
zbMATH Keywords: computational geometry
MaRDI profile type: Publication
full work available at URL: s00453-015-0058-y
OpenAlex ID: W2165366584
cites work: Visibility of disjoint polygons
cites work: An optimal parallel algorithm for the visibility of a simple polygon from a point
cites work: Visibility-based planning of sensor control strategies
cites work: Triangulating a simple polygon in linear time
cites work: Visibility and intersection problems in plane geometry
cites work: A Nearly Optimal Algorithm for Finding L 1 Shortest Paths among Polygonal Obstacles in the Plane
cites work: Visibility and ray shooting queries in polygonal domains
cites work: Weak visibility queries of line segments in simple polygons
cites work: A linear algorithm for computing the visibility polygon from a point
cites work: Computing the visibility polygon from a convex set and related problems
cites work: An Output-Sensitive Algorithm for Computing Visibility Graphs
cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
cites work: An Optimal Algorithm for Computing Visibility in the Plane
cites work: Planar rectilinear shortest path computation using corridors
cites work: On the correctness of a linear-time visibility polygon algorithm∗
cites work: Corrections to Lee's visibility polygon algorithm
cites work: An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
cites work: Visibility of a simple polygon
cites work: Computing the visibility polygon from an edge
cites work: Shortest paths in the plane with convex polygonal obstacles
cites work: Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
DOI: 10.1007/S00453-015-0058-Y
description: scientific article; zbMATH DE number 6691976