Space/query-time tradeoff for computing the visibility polygon

In this paper, we consider the problem of computing the visibility polygon (VP) of a query point q   (or VP(q)VP(q)) in a scene consisting of some obstacles with total complexity of n  . We show that the combinatorial representation of VP(q)VP(q) can be computed in logarithmic time by preprocessing the scene in O(n4logn) time and using O(n4)O(n4) space. We can also report the actual VP(q)VP(q) in additional O(|VP(q)|)O(|VP(q)|) time. As a main result of this paper, we will prove that we can have a tradeoff between the query time and the preprocessing time/space. In other words, we will show that using O(m)O(m) space, we can obtain O(n2log(m/n)/m) query time, where m   is a parameter satisfying n2⩽m⩽n4n2⩽m⩽n4. For example, when m=n3m=n3, the query time of our algorithm is O(nlogn), that improves the query time of the only available algorithm with this memory usage (Zarei and Ghodsi, 2008 [26]), which degrades to O(nlogn) in the worst case. An elegant feature of our algorithm that makes it useful in many applications is that it can determine the properties of the VP without actually computing it.