Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time

M. Fischer, T. Lukovszki, M. Ziegler, in: Algorithms — ESA’ 98, Berlin, Heidelberg, 1998.

Download
Restricted hni-id-854.pdf 266.07 KB
Book Chapter | Published | English
Author
; ;
Abstract
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.
Publishing Year
Book Title
Algorithms — ESA’ 98
ISSN
LibreCat-ID

Cite this

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
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
@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} }
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.
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.
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.
Main File(s)
File Name
hni-id-854.pdf 266.07 KB
Access Level
Restricted Closed Access
Last Uploaded
2020-08-27T11:20:38Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search