Third International Workshop on Frontiers in Algorithmics , 2009-06-20

Title : ( Space–Query-Time Tradeoff for Computing the Visibility Polygon )

Authors: Mostafa Nouri Baygi , Mohammad Ghodsi ,

Citation: BibTeX | EndNote

Abstract

Computing the visibility polygon, VP, of a point in a polygonal scene, is a classical problem that has been studied extensively. In this paper, we consider the problem of computing VP for any query point efficiently, with some additional preprocessing phase. The scene consists of a set of obstacles, of total complexity O(n). We show for a query point q, VP(q) can be computed in logarithmic time using O(n 4) space and O(n 4 logn) preprocessing time. Furthermore to decrease space usage and preprocessing time, we make a tradeoff between space usage and query time; so by spending O(m) space, we can achieve O(n2log(√m/n)/√m) query time, where n 2 ≤ m ≤ n 4. These results are also applied to angular sorting of a set of points around a query point.

Keywords

, Visibility polygon, logarithmic query time, space–query-time tradeoff, (1/r)-cutting
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@inproceedings{paperid:1038801,
author = {Nouri Baygi, Mostafa and Mohammad Ghodsi},
title = {Space–Query-Time Tradeoff for Computing the Visibility Polygon},
booktitle = {Third International Workshop on Frontiers in Algorithmics},
year = {2009},
location = {هفی},
keywords = {Visibility polygon;logarithmic query time; space–query-time tradeoff; (1/r)-cutting},
}

[Download]

%0 Conference Proceedings
%T Space–Query-Time Tradeoff for Computing the Visibility Polygon
%A Nouri Baygi, Mostafa
%A Mohammad Ghodsi
%J Third International Workshop on Frontiers in Algorithmics
%D 2009

[Download]