---
_id: '18346'
abstract:
- lang: eng
  text: "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<n is an arbitrary parameter. We describe an\r\nimplementation of this
    approach and demonstrate the practical benefit of the\r\nparameter k to trade
    memory for query time in an empirical evaluation on three\r\nclasses of benchmark
    scenes."
author:
- first_name: Matthias
  full_name: Fischer, Matthias
  id: '146'
  last_name: Fischer
- first_name: Matthias
  full_name: Hilbig, Matthias
  last_name: Hilbig
- first_name: Claudius
  full_name: Jähn, Claudius
  last_name: Jähn
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Martin
  full_name: Ziegler, Martin
  last_name: Ziegler
citation:
  ama: 'Fischer M, Hilbig M, Jähn C, Meyer auf der Heide F, Ziegler M. Planar Visibility
    Counting. In: <i>Proc. 25th European Workshop on Computational Geometry</i>. ;
    2009:203-206.'
  apa: Fischer, M., Hilbig, M., Jähn, C., Meyer auf der Heide, F., &#38; Ziegler,
    M. (2009). Planar Visibility Counting. In <i>Proc. 25th European Workshop on Computational
    Geometry</i> (pp. 203–206).
  bibtex: '@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}
    }'
  chicago: Fischer, Matthias, Matthias Hilbig, Claudius Jähn, Friedhelm Meyer auf
    der Heide, and Martin Ziegler. “Planar Visibility Counting.” In <i>Proc. 25th
    European Workshop on Computational Geometry</i>, 203–6, 2009.
  ieee: M. Fischer, M. Hilbig, C. Jähn, F. Meyer auf der Heide, and M. Ziegler, “Planar
    Visibility Counting,” in <i>Proc. 25th European Workshop on Computational Geometry</i>,
    2009, pp. 203–206.
  mla: Fischer, Matthias, et al. “Planar Visibility Counting.” <i>Proc. 25th European
    Workshop on Computational Geometry</i>, 2009, pp. 203–06.
  short: '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.'
date_created: 2020-08-26T08:49:50Z
date_updated: 2022-01-06T06:53:29Z
department:
- _id: '63'
language:
- iso: eng
page: 203-206
publication: Proc. 25th European Workshop on Computational Geometry
status: public
title: Planar Visibility Counting
type: conference
user_id: '15415'
year: '2009'
...