Weak visibility queries of line segments in simple polygons and polygonal domains

ABSTRACT

In this paper we consider the problem of computing the weak visibility polygon of a query line segment pq (or $\mathrm{WVP}\left(pq\right)$) inside a given polygon $\mathcal{P}$. Our first algorithm runs in simple polygons and needs $O(n^3\log n)$ time and $O\left(n^3\right)$ space in the preprocessing phase to report $\mathrm{WVP}\left(pq\right)$ of any query line segment pq in time $O(\log n+|\mathrm{WVP}(pq\left)|\right)$. We also give an algorithm to compute the weak visibility polygon of a query line segment in a non-simple polygon with $h\ge 1$ pairwise-disjoint polygonal obstacles with a total of n vertices. Our algorithm needs $O(n^2\log n)$ time and $O\left(n^2\right)$ space in the preprocessing phase and $\mathrm{WVP}\left(pq\right)$ in query time of $O(n{h}^{\prime }\log n+k)$, in which $h^{\prime }$ is an output sensitive parameter of at most $min(h,k)$, and $k=O\left(n^2{h}^2\right)$ is the output size.

KEYWORDS:

• Computational geometry
• visibility
• line segment visibility
• simple polygons

2010 AMS Subject Classifications:

• 68U05
• 65D18

Disclosure statement

No potential conflict of interest was reported by the authors.