Computational Geometry, ( ISI ), Volume (46), No (3), Year (2013-4) , Pages (371-381)

Title : ( Space/query-time tradeoff for computing the visibility polygon )

Authors: Mostafa Nouri Baygi , Mohammad Ghodsi ,

Citation: BibTeX | EndNote


In this paper, we consider the problem of computing the visibility polygon (VP) of a query point q (or VP(q)) in a scene consisting of some obstacles with total complexity of n. We show that the combinatorial representation of VP(q) can be computed in logarithmic time by preprocessing the scene in O(n^4 log n) time and using O(n^4) space. We can also report the actual VP(q) in additional 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) space, we can obtain O(n^2 log(\\sqrt m/n) / \\sqrt m) query time, where m is a parameter satisfying n^2⩽m⩽n^4. For example, when m=n^3, the query time of our algorithm is O(\\sqrt n log \\sqrt n), that improves the query time of the only available algorithm with this memory usage (Zarei and Ghodsi, 2008 [26]), which degrades to O(n log n) 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.


, Visibility polygon; Logarithmic query time; Space/query, time tradeoff
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

author = {Nouri Baygi, Mostafa and Mohammad Ghodsi},
title = {Space/query-time tradeoff for computing the visibility polygon},
journal = {Computational Geometry},
year = {2013},
volume = {46},
number = {3},
month = {April},
issn = {0925-7721},
pages = {371--381},
numpages = {10},
keywords = {Visibility polygon; Logarithmic query time; Space/query-time tradeoff},


%0 Journal Article
%T Space/query-time tradeoff for computing the visibility polygon
%A Nouri Baygi, Mostafa
%A Mohammad Ghodsi
%J Computational Geometry
%@ 0925-7721
%D 2013