Planar Visibility Counting
M. Fischer, M. Hilbig, C. Jähn, F. Meyer auf der Heide, M. Ziegler, in: Proc. 25th European Workshop on Computational Geometry, 2009, pp. 203–206.
Download
No fulltext has been uploaded.
Conference Paper
| 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
Proceedings Title
Proc. 25th European Workshop on Computational Geometry
Page
203-206
LibreCat-ID
Cite this
Fischer M, Hilbig M, Jähn C, Meyer auf der Heide F, Ziegler M. Planar Visibility Counting. In: Proc. 25th European Workshop on Computational Geometry. ; 2009:203-206.
Fischer, M., Hilbig, M., Jähn, C., Meyer auf der Heide, F., & Ziegler, M. (2009). Planar Visibility Counting. In Proc. 25th European Workshop on Computational Geometry (pp. 203–206).
@inproceedings{Fischer_Hilbig_Jähn_Meyer auf der Heide_Ziegler_2009, title={Planar Visibility Counting}, booktitle={Proc. 25th European Workshop on Computational Geometry}, author={Fischer, Matthias and Hilbig, Matthias and Jähn, Claudius and Meyer auf der Heide, Friedhelm and Ziegler, Martin}, year={2009}, pages={203–206} }
Fischer, Matthias, Matthias Hilbig, Claudius Jähn, Friedhelm Meyer auf der Heide, and Martin Ziegler. “Planar Visibility Counting.” In Proc. 25th European Workshop on Computational Geometry, 203–6, 2009.
M. Fischer, M. Hilbig, C. Jähn, F. Meyer auf der Heide, and M. Ziegler, “Planar Visibility Counting,” in Proc. 25th European Workshop on Computational Geometry, 2009, pp. 203–206.
Fischer, Matthias, et al. “Planar Visibility Counting.” Proc. 25th European Workshop on Computational Geometry, 2009, pp. 203–06.