---
_id: '3026'
author:
- first_name: Johannes
full_name: Blömer, Johannes
id: '23'
last_name: Blömer
citation:
ama: 'Blömer J. A Probabilistic Zero-Test for Expressions Involving Roots of Rational
Numbers. In: Algorithms — ESA’ 98. Berlin, Heidelberg: Springer Berlin
Heidelberg; 2007:151-162. doi:10.1007/3-540-68530-8_13'
apa: 'Blömer, J. (2007). A Probabilistic Zero-Test for Expressions Involving Roots
of Rational Numbers. In Algorithms — ESA’ 98 (pp. 151–162). Berlin, Heidelberg:
Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-68530-8_13'
bibtex: '@inbook{Blömer_2007, place={Berlin, Heidelberg}, title={A Probabilistic
Zero-Test for Expressions Involving Roots of Rational Numbers}, DOI={10.1007/3-540-68530-8_13},
booktitle={Algorithms — ESA’ 98}, publisher={Springer Berlin Heidelberg}, author={Blömer,
Johannes}, year={2007}, pages={151–162} }'
chicago: 'Blömer, Johannes. “A Probabilistic Zero-Test for Expressions Involving
Roots of Rational Numbers.” In Algorithms — ESA’ 98, 151–62. Berlin, Heidelberg:
Springer Berlin Heidelberg, 2007. https://doi.org/10.1007/3-540-68530-8_13.'
ieee: 'J. Blömer, “A Probabilistic Zero-Test for Expressions Involving Roots of
Rational Numbers,” in Algorithms — ESA’ 98, Berlin, Heidelberg: Springer
Berlin Heidelberg, 2007, pp. 151–162.'
mla: Blömer, Johannes. “A Probabilistic Zero-Test for Expressions Involving Roots
of Rational Numbers.” Algorithms — ESA’ 98, Springer Berlin Heidelberg,
2007, pp. 151–62, doi:10.1007/3-540-68530-8_13.
short: 'J. Blömer, in: Algorithms — ESA’ 98, Springer Berlin Heidelberg, Berlin,
Heidelberg, 2007, pp. 151–162.'
date_created: 2018-06-05T08:28:39Z
date_updated: 2022-01-06T06:58:51Z
department:
- _id: '64'
doi: 10.1007/3-540-68530-8_13
page: 151-162
place: Berlin, Heidelberg
publication: Algorithms — ESA’ 98
publication_identifier:
isbn:
- '9783540648482'
- '9783540685302'
issn:
- 0302-9743
publication_status: published
publisher: Springer Berlin Heidelberg
status: public
title: A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers
type: book_chapter
user_id: '25078'
year: '2007'
...
---
_id: '17412'
abstract:
- lang: eng
text: "We study algorithmic aspects in the management of geometric scenes in interactive
walkthrough animations. We consider arbitrarily large scenes consisting of unit
size balls. For a smooth navigation in the scene we have to fulfill hard real
time requirements. Therefore, we need algorithms whose running time is independent
of the total number of objects in the scene and that use as small space as possible.
In this work we focus on one of the basic operations in our walkthrough system:
reporting the objects around the visitor within a certain distance. Previously
a randomized data structure was presented that supports reporting the balls around
the visitor in an output sensitive time and allows insertion and deletion of objects
nearly as fast as searching. These results were achieved by exploiting the fact
that the visitor moves ''slowly'' through the scene. A serious disadvantage of
the aforementioned data structure is a big space overhead and the use of randomization.
Our first result is a construction of weak spanners that leads to an improvement
of the space requirement of the previously known data structures. Then we develop
a deterministic data structure for the searching problem in which insertion of
objects are allowed. Our incremental data structure supports O(1+k) reporting
time, where k is a certain quantity close to the number of reported objects. The
insertion time is similar to the reporting time and the space is linear to the
total number of objects.\r\n"
author:
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Tamás
full_name: Lukovszki, Tamás
last_name: Lukovszki
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: 'Fischer M, Lukovszki T, Ziegler M. Geometric Searching in Walkthrough Animations
with Weak Spanners in Real Time. In: Algorithms — ESA’ 98. Berlin, Heidelberg;
1998. doi:10.1007/3-540-68530-8_14'
apa: Fischer, M., Lukovszki, T., & Ziegler, M. (1998). Geometric Searching in
Walkthrough Animations with Weak Spanners in Real Time. In Algorithms — ESA’
98. Berlin, Heidelberg. https://doi.org/10.1007/3-540-68530-8_14
bibtex: '@inbook{Fischer_Lukovszki_Ziegler_1998, place={Berlin, Heidelberg}, title={Geometric
Searching in Walkthrough Animations with Weak Spanners in Real Time}, DOI={10.1007/3-540-68530-8_14},
booktitle={Algorithms — ESA’ 98}, author={Fischer, Matthias and Lukovszki, Tamás
and Ziegler, Martin}, year={1998} }'
chicago: Fischer, Matthias, Tamás Lukovszki, and Martin Ziegler. “Geometric Searching
in Walkthrough Animations with Weak Spanners in Real Time.” In Algorithms —
ESA’ 98. Berlin, Heidelberg, 1998. https://doi.org/10.1007/3-540-68530-8_14.
ieee: M. Fischer, T. Lukovszki, and M. Ziegler, “Geometric Searching in Walkthrough
Animations with Weak Spanners in Real Time,” in Algorithms — ESA’ 98, Berlin,
Heidelberg, 1998.
mla: Fischer, Matthias, et al. “Geometric Searching in Walkthrough Animations with
Weak Spanners in Real Time.” Algorithms — ESA’ 98, 1998, doi:10.1007/3-540-68530-8_14.
short: 'M. Fischer, T. Lukovszki, M. Ziegler, in: Algorithms — ESA’ 98, Berlin,
Heidelberg, 1998.'
date_created: 2020-07-27T11:42:54Z
date_updated: 2022-01-06T06:53:11Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/3-540-68530-8_14
file:
- access_level: closed
content_type: application/pdf
creator: koala
date_created: 2020-08-27T11:20:38Z
date_updated: 2020-08-27T11:20:38Z
file_id: '18442'
file_name: hni-id-854.pdf
file_size: 266070
relation: main_file
success: 1
file_date_updated: 2020-08-27T11:20:38Z
has_accepted_license: '1'
language:
- iso: eng
place: Berlin, Heidelberg
publication: Algorithms — ESA’ 98
publication_identifier:
isbn:
- '9783540648482'
- '9783540685302'
issn:
- 0302-9743
publication_status: published
status: public
title: Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time
type: book_chapter
user_id: '15415'
year: '1998'
...