Weak visibility queries of line segments in simple polygons and polygonal domains. Issue 4 (3rd April 2018)

• Record Type: Journal Article
• Authors: Nouri Bygi, M.; Ghodsi, M.
• Is Part Of: International journal of computer mathematics. Volume 95:Issue 4(2018)
• Page Start: 721
• Page End: 738
• Publication Date: 2018-04-03
• Subjects: Computational geometry -- visibility -- line segment visibility -- simple polygons; 68U05 -- 65D18; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2017.1296139
• Languages: English
• ISSNs: 0020-7160

Abstract

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.