Intersection queries in sets of disks. (English) Zbl 0761.68098
Summary: We develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report all \(k\) disks interesting a query line segment in time \(O(n^{\beta+\varepsilon}+k)\), where \(n\) is the number of disks, \(\beta=\log_ 2(1+\sqrt{5})-1\approx 0.695\), and \(\varepsilon\) is an arbitrarily small positive constant. If the segment is a full line, the query time becomes \(O(n^ \beta+k)\). For intersecting disks we obtain an \(O(n \log n)\) size data structure that can answer an intersection query in time \(O(n^{2/3}\log^ 2n+k)\). We also present a linear size data structure for ray shooting queries, whose query time is \(O(n^ \beta)\).
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68P05 | Data structures |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Agarwal, P. K.,Ray shooting and other applications of spanning trees with low stabbing number, Proc. 5th Ann. Symp. on Comp. Geometry (1989), pp. 315–325. (Also to appear in SIAM J. Computing.) |
| [2] | Agarwal, P. K., M. van Kreveld and M. Overmars,Storing and searching in curved objects, Proc. 7th Ann. Symp. on Comp. Geometry (1991), pp. 41–50. |
| [3] | Chazelle, B. and J. Friedman,A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990), pp. 229–249. · Zbl 0715.68036 · doi:10.1007/BF02122778 |
| [4] | Chazelle, B., H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir and J. Snoeyink,Ray shooting in polygons using geodesic triangulations, Proc. ICALP, Lect. Notes in Comp. Science 510 (1991) pp. 661–673. · Zbl 0769.68119 |
| [5] | Chazelle, B. and L. J. Guibas,Fractional cascading: I. A data structuring technique, Algorithmica 1 (1986), pp. 133–162. · Zbl 0639.68056 · doi:10.1007/BF01840440 |
| [6] | Chazelle, B. and E. Welzl,Quasi-optimal range searching in spaces of finite VC-dimension, Discr. & Comp. Geometry 4 (1989), pp. 467–489. · Zbl 0681.68081 · doi:10.1007/BF02187743 |
| [7] | Cole, R.,Searching and storing similar lists. J. of Algorithms 7 (1986), pp. 202–220. · Zbl 0605.68053 · doi:10.1016/0196-6774(86)90004-0 |
| [8] | Dobkin, D. P. and H. Edelsbrunner,Space searching for intersecting objects, J. of Algorithms 8 (1987), pp. 348–361. · Zbl 0646.68077 · doi:10.1016/0196-6774(87)90015-0 |
| [9] | Edelsbrunner, H.,Algorithms in combinatorial Geometry, Springer-Verlag, Berlin, 1987. · Zbl 0634.52001 |
| [10] | Edelsbrunner, H., L. J. Guibas and J. Stolfi,Optimal point location in a monotone subdivision, SIAM J. Comput. 15 (1986), pp. 317–340. · Zbl 0602.68102 · doi:10.1137/0215023 |
| [11] | Edelsbrunner, H. and E. Welzl,Halfplanar range search in linear space and O 0.695)query time, Inf. Proc. Lett. 23 (1986), pp. 289–293. · Zbl 0634.68064 · doi:10.1016/0020-0190(86)90088-8 |
| [12] | Guibas, L., M. Overmars and M. Sharir,Ray shooting, implicit point location, and related queries in arrangements of segments, Techn. Rep. No. 433, New York University, 1989. |
| [13] | Haussler, D. and E. Welzl,{\(\epsilon\)}-nets and simplex range queries, Discr. & Comp. Geometry 2 (1987), pp. 127–151. · Zbl 0619.68056 · doi:10.1007/BF02187876 |
| [14] | Kedem, K., R. Livne, J. Pach and M. Sharir,On the union of Jordan regions and collision-free translational motion amidst polygonal obstacless, Discr. & Comp. Geometry 1 (1986), 59–71. · Zbl 0594.52004 · doi:10.1007/BF02187683 |
| [15] | Overmars, M. H., H. Schipper and M. Sharir,Storing line segments in partition trees, BIT 30 (1990), pp. 385–403. · Zbl 0696.68068 · doi:10.1007/BF01931656 |
| [16] | Sharir, M.,On k-sets in arrangements of curves and surfaces, to appear in Discr. & Comp. Geometry. · Zbl 0744.68132 |
| [17] | Snoeyink, J., personal communication. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
