Weak visibility queries of line segments in simple polygons and polygonal domains. Issue 4 (3rd April 2018) - Nouri Bygi, M.
ABSTRACT: In this paper we consider the problem of computing the weak visibility polygon of a query line segment pq (orWVP ( p q ) ) inside a given polygonP . Our first algorithm runs in simple polygons and needsO ( n 3 log ⁡ n ) time andO ( n 3 ) space in the preprocessing phase to reportWVP ( p q ) of any query line segment pq in timeO ( log ⁡ n + | WVP ( p q ) | ) . We also give an algorithm to compute the weak visibility polygon of a query line segment in a non-simple polygon withh ≥ 1 pairwise-disjoint polygonal obstacles with a total of n vertices. Our algorithm needsO ( n 2 log ⁡ n ) time andO ( n 2 ) space in the preprocessing phase andWVP ( p q ) in query time ofO ( n h ′ log ⁡ n + k ), in whichh ′ is an output sensitive parameter of at mostmin ( h, k ), andk = O ( n 2 h 2 ) is the output size.