---
_id: '18867'
abstract:
- lang: eng
  text: Modern computer graphics systems are able to render sophisticated 3D szenes
    consisting of millions of polygons. In this paper we address the problem of occlusion
    culling. Aila, Miettinen, and Nordlund suggested to implement a FIFO buffer on
    graphics cards which is able to delay the polygons before drawing them. When one
    of the polygons within the buffer is occluded or masked by another polygon arriving
    later from the application, the rendering engine can drop the occluded one without
    rendering, saving important rendering time.<br>We introduce a theoretical online
    model to analyse these problems in theory using competitive analysis. For different
    cost measures addressed we invent the first competitive algorithms for online
    occlusion culling. Our implementation shows that these algorithms outperform known
    ones for real 3D scenes as well.
author:
- first_name: Gereon
  full_name: Frahling, Gereon
  last_name: Frahling
- first_name: Jens
  full_name: Krokowski, Jens
  last_name: Krokowski
citation:
  ama: 'Frahling G, Krokowski J. Online Occlusion Culling. In: <i>Proc. of the 13th
    Annual European Symposium on Algorithms (ESA 2005)</i>. Vol 3669. Berlin, Heidelberg:
    Springer; 2005:758-769. doi:<a href="https://doi.org/10.1007/11561071_67">10.1007/11561071_67</a>'
  apa: 'Frahling, G., &#38; Krokowski, J. (2005). Online Occlusion Culling. In <i>Proc.
    of the 13th Annual European Symposium on Algorithms (ESA 2005)</i> (Vol. 3669,
    pp. 758–769). Berlin, Heidelberg: Springer. <a href="https://doi.org/10.1007/11561071_67">https://doi.org/10.1007/11561071_67</a>'
  bibtex: '@inproceedings{Frahling_Krokowski_2005, place={Berlin, Heidelberg}, title={Online
    Occlusion Culling}, volume={3669}, DOI={<a href="https://doi.org/10.1007/11561071_67">10.1007/11561071_67</a>},
    booktitle={Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)},
    publisher={Springer}, author={Frahling, Gereon and Krokowski, Jens}, year={2005},
    pages={758–769} }'
  chicago: 'Frahling, Gereon, and Jens Krokowski. “Online Occlusion Culling.” In <i>Proc.
    of the 13th Annual European Symposium on Algorithms (ESA 2005)</i>, 3669:758–69.
    Berlin, Heidelberg: Springer, 2005. <a href="https://doi.org/10.1007/11561071_67">https://doi.org/10.1007/11561071_67</a>.'
  ieee: G. Frahling and J. Krokowski, “Online Occlusion Culling,” in <i>Proc. of the
    13th Annual European Symposium on Algorithms (ESA 2005)</i>, 2005, vol. 3669,
    pp. 758–769.
  mla: Frahling, Gereon, and Jens Krokowski. “Online Occlusion Culling.” <i>Proc.
    of the 13th Annual European Symposium on Algorithms (ESA 2005)</i>, vol. 3669,
    Springer, 2005, pp. 758–69, doi:<a href="https://doi.org/10.1007/11561071_67">10.1007/11561071_67</a>.
  short: 'G. Frahling, J. Krokowski, in: Proc. of the 13th Annual European Symposium
    on Algorithms (ESA 2005), Springer, Berlin, Heidelberg, 2005, pp. 758–769.'
date_created: 2020-09-02T13:26:52Z
date_updated: 2022-01-06T06:53:53Z
department:
- _id: '63'
doi: 10.1007/11561071_67
intvolume: '      3669'
language:
- iso: eng
page: 758-769
place: Berlin, Heidelberg
publication: Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)
publication_identifier:
  isbn:
  - '9783540291183'
  - '9783540319511'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
publisher: Springer
status: public
title: Online Occlusion Culling
type: conference
user_id: '15415'
volume: 3669
year: '2005'
...
---
_id: '18915'
abstract:
- lang: eng
  text: We present a simple two-person Bucket Game, based on throwing balls into buckets,
    and we<br>discuss possible players' strategies.<br><br>We use these strategies
    to create an approximation algorithm for a generalization of<br>the well known
    Set Cover problem, where we need to cover each element by at least $k$ sets.<br>Furthermore,
    we apply these strategies to construct a randomized algorithm for Dynamic Page
    Migration <br>problem achieving the optimal competitive ratio against an oblivious
    adversary.
author:
- first_name: Marcin
  full_name: Bienkowski, Marcin
  last_name: Bienkowski
- first_name: Jarosław
  full_name: Byrka, Jarosław
  last_name: Byrka
citation:
  ama: 'Bienkowski M, Byrka J. Bucket Game with Applications to Set Multicover and
    Dynamic Page Migration. In: <i>Proc. of the 13th Annual European Symposium on
    Algorithms (ESA 2005)</i>. Vol 3669. Berlin, Heidelberg: Springer ; 2005:815-826.
    doi:<a href="https://doi.org/10.1007/11561071_72">10.1007/11561071_72</a>'
  apa: 'Bienkowski, M., &#38; Byrka, J. (2005). Bucket Game with Applications to Set
    Multicover and Dynamic Page Migration. In <i>Proc. of the 13th Annual European
    Symposium on Algorithms (ESA 2005)</i> (Vol. 3669, pp. 815–826). Berlin, Heidelberg:
    Springer . <a href="https://doi.org/10.1007/11561071_72">https://doi.org/10.1007/11561071_72</a>'
  bibtex: '@inproceedings{Bienkowski_Byrka_2005, place={Berlin, Heidelberg}, title={Bucket
    Game with Applications to Set Multicover and Dynamic Page Migration}, volume={3669},
    DOI={<a href="https://doi.org/10.1007/11561071_72">10.1007/11561071_72</a>}, booktitle={Proc.
    of the 13th Annual European Symposium on Algorithms (ESA 2005)}, publisher={Springer
    }, author={Bienkowski, Marcin and Byrka, Jarosław}, year={2005}, pages={815–826}
    }'
  chicago: 'Bienkowski, Marcin, and Jarosław Byrka. “Bucket Game with Applications
    to Set Multicover and Dynamic Page Migration.” In <i>Proc. of the 13th Annual
    European Symposium on Algorithms (ESA 2005)</i>, 3669:815–26. Berlin, Heidelberg:
    Springer , 2005. <a href="https://doi.org/10.1007/11561071_72">https://doi.org/10.1007/11561071_72</a>.'
  ieee: M. Bienkowski and J. Byrka, “Bucket Game with Applications to Set Multicover
    and Dynamic Page Migration,” in <i>Proc. of the 13th Annual European Symposium
    on Algorithms (ESA 2005)</i>, 2005, vol. 3669, pp. 815–826.
  mla: Bienkowski, Marcin, and Jarosław Byrka. “Bucket Game with Applications to Set
    Multicover and Dynamic Page Migration.” <i>Proc. of the 13th Annual European Symposium
    on Algorithms (ESA 2005)</i>, vol. 3669, Springer , 2005, pp. 815–26, doi:<a href="https://doi.org/10.1007/11561071_72">10.1007/11561071_72</a>.
  short: 'M. Bienkowski, J. Byrka, in: Proc. of the 13th Annual European Symposium
    on Algorithms (ESA 2005), Springer , Berlin, Heidelberg, 2005, pp. 815–826.'
date_created: 2020-09-03T08:11:11Z
date_updated: 2022-01-06T06:53:54Z
department:
- _id: '63'
doi: 10.1007/11561071_72
intvolume: '      3669'
language:
- iso: eng
page: 815-826
place: Berlin, Heidelberg
publication: Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)
publication_identifier:
  isbn:
  - '9783540291183'
  - '9783540319511'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
publisher: 'Springer '
status: public
title: Bucket Game with Applications to Set Multicover and Dynamic Page Migration
type: conference
user_id: '15415'
volume: 3669
year: '2005'
...