Near optimal line segment queries in simple polygons

• We consider the weak visibility queries of line segments in simple polygons.
• We present near optimal algorithm for the problem.
• The preprocessing time of the current results is improved.

This paper considers the problem of computing the weak visibility polygon (WVP) of any query line segment pq   (or WVP(pq)WVP(pq)) inside a given simple polygon P. We present an algorithm that preprocesses P   and creates a data structure from which WVP(pq)WVP(pq) is efficiently reported in an output sensitive manner.Our algorithm needs O(n2log⁡n)O(n2log⁡n) time and O(n2)O(n2) space in the preprocessing phase to report WVP(pq)WVP(pq) of any query line segment pq   in time O(|WVP(pq)|+log2⁡n+κlog2⁡(nκ)), where κ   is an input and output sensitive parameter of at most |WVP(pq)||WVP(pq)|. We improve the preprocessing time and space of current results for this problem [11] and [6] at the expense of more query time.