Planar Visibility Counting

M. Fischer, M. Hilbig, C. Jähn, F. Meyer auf der Heide, M. Ziegler, ArXiv:0810.0052 (2008).

No fulltext has been uploaded.
Preprint | English
Fischer, MatthiasLibreCat; Hilbig, Matthias; Jähn, Claudius; Meyer auf der Heide, FriedhelmLibreCat; Ziegler, Martin
For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.
Publishing Year
Journal Title

Cite this

Fischer M, Hilbig M, Jähn C, Meyer auf der Heide F, Ziegler M. Planar Visibility Counting. arXiv:08100052. 2008.
Fischer, M., Hilbig, M., Jähn, C., Meyer auf der Heide, F., & Ziegler, M. (2008). Planar Visibility Counting. ArXiv:0810.0052.
@article{Fischer_Hilbig_Jähn_Meyer auf der Heide_Ziegler_2008, title={Planar Visibility Counting}, journal={arXiv:0810.0052}, author={Fischer, Matthias and Hilbig, Matthias and Jähn, Claudius and Meyer auf der Heide, Friedhelm and Ziegler, Martin}, year={2008} }
Fischer, Matthias, Matthias Hilbig, Claudius Jähn, Friedhelm Meyer auf der Heide, and Martin Ziegler. “Planar Visibility Counting.” ArXiv:0810.0052, 2008.
M. Fischer, M. Hilbig, C. Jähn, F. Meyer auf der Heide, and M. Ziegler, “Planar Visibility Counting,” arXiv:0810.0052. 2008.
Fischer, Matthias, et al. “Planar Visibility Counting.” ArXiv:0810.0052, 2008.


Marked Publications

Open Data LibreCat


arXiv 0810.0052

Search this title in

Google Scholar