@inproceedings{19901,
author = {Raptopoulos, Christoforos L. and Nikoletseas, Sotiris E. and Spirakis, Paul G.},
booktitle = {34st International Symposium on Mathematical Foundations of Computer Science},
isbn = {9781493928637},
pages = {600----611},
title = {{Colouring Non-sparse Random Intersection Graphs}},
doi = {10.1007/978-1-4939-2864-4_597},
year = {2009},
}
@inproceedings{18346,
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