Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles International Journal of Computational Geometry and Applications Year : 2007

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint

Abstract

Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In linear space, and after O(n log n) preprocessing time, our solution maintains the view at a cost of O(log n) amortized time (resp. O(log^2 n) worst case time) for each change. Our algorithm can also be used to maintain the set of points sorted according to their distance to q.
Fichier principal
Vignette du fichier
hal.pdf (129.42 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00192927 , version 1 (29-11-2007)

Identifiers

Cite

Olivier Devillers, Vida Dujmovic, Hazel Everett, Samuel Hornus, Sue Whitesides, et al.. Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint. International Journal of Computational Geometry and Applications, 2007, 17 (4), pp.297-304. ⟨10.1142/S0218195907002343⟩. ⟨inria-00192927⟩
417 View
424 Download

Altmetric

Share

Gmail Facebook X LinkedIn More