---
res:
bibo_abstract:
- "For a fixed virtual scene (=collection of simplices) S and given observer\r\nposition
p, how many elements of S are weakly visible (i.e. not fully occluded\r\nby others)
from p? The present work explores the trade-off between query time\r\nand preprocessing
space for these quantities in 2D: exactly, in the approximate\r\ndeterministic,
and in the probabilistic sense. We deduce the EXISTENCE of an\r\nO(m^2/n^2) space
data structure for S that, given p and time O(log n), allows\r\nto approximate
the ratio of occluded segments up to arbitrary constant absolute\r\nerror; here
m denotes the size of the Visibility Graph--which may be quadratic,\r\nbut typically
is just linear in the size n of the scene S. On the other hand,\r\nwe present
a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k)\r\npreprocessing
time and space with similar approximation properties and query\r\ntime O(k*polylog
n), where k