Planar Visibility Counting

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

Download
No fulltext has been uploaded.
Preprint | English
Author
Fischer, MatthiasLibreCat; Hilbig, Matthias; Jähn, Claudius; Meyer auf der Heide, FriedhelmLibreCat; Ziegler, Martin
Abstract
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
arXiv:0810.0052
LibreCat-ID

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.

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 0810.0052

Search this title in

Google Scholar