Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Space–Query-Time Tradeoff for Computing the Visibility Polygon
verfasst von : Mostafa Nouri, Mohammad Ghodsi
Erschienen in: Frontiers in Algorithmics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
log
n
) 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(n^2 \log (\sqrt{m}/n) / \sqrt{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.