Zooming by repeated range detection

H. Edelsbrunner, M. Overmars, Information Processing Letters 24 (1987) 413–417.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Abstract
In a number of recent papers, techniques from computational geometry (the field of algorithm design that deals with objects in multi-dimensional space) have been applied to some problems in the area of computer graphics. In this way, efficient solutions were obtained for the windowing problem that asks for those line segments in a planar set that lie in given window (range) and the moving problem that asks for the first line segment that comes into the window when moving the window in some direction. In this paper we show that also the zooming problem, which asks for the first line segment that comes into the window when we enlarge it, can be solved efficiently. This is done by repeatedly performing range queries with ranges of varying sizes. The obtained structure is dynamic and yields a query time of O(log2n) and an insertion and deletion time of O(log2n), where n is the number of line segments in the set. The amount of storage required is O(n log n). It is also shown that the technique of repeated range search can be used to solve several other problems efficiently.
Publishing Year
Date Published
1987-04-06
Journal Title
Information Processing Letters
Volume
24
Issue
6
Page
413 - 417
IST-REx-ID

Cite this

Edelsbrunner H, Overmars M. Zooming by repeated range detection. Information Processing Letters. 1987;24(6):413-417. doi:10.1016/0020-0190(87)90120-7
Edelsbrunner, H., & Overmars, M. (1987). Zooming by repeated range detection. Information Processing Letters, 24(6), 413–417. https://doi.org/10.1016/0020-0190(87)90120-7
Edelsbrunner, Herbert, and Mark Overmars. “Zooming by Repeated Range Detection.” Information Processing Letters 24, no. 6 (1987): 413–17. https://doi.org/10.1016/0020-0190(87)90120-7.
H. Edelsbrunner and M. Overmars, “Zooming by repeated range detection,” Information Processing Letters, vol. 24, no. 6, pp. 413–417, 1987.
Edelsbrunner H, Overmars M. 1987. Zooming by repeated range detection. Information Processing Letters. 24(6), 413–417.
Edelsbrunner, Herbert, and Mark Overmars. “Zooming by Repeated Range Detection.” Information Processing Letters, vol. 24, no. 6, Elsevier, 1987, pp. 413–17, doi:10.1016/0020-0190(87)90120-7.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar