Abstract
Space-efficient algorithms are presented for a number of intersection searching problems in the plane, including, ray-shooting, segment intersection searching, triangle stabbing, and triangle range searching. The algorithms for ray-shooting and segment intersection searching are improvements upon the results given previously in [Aga89]. All the algorithms can be dynamized efficiently by taking advantage of their decomposability. Several applications of the above results are presented.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 |
| Publisher | Association for Computing Machinery |
| Pages | 7-16 |
| Number of pages | 10 |
| ISBN (Print) | 0897913760 |
| State | Published - Mar 1 1991 |
| Event | 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States Duration: Jan 28 1991 → Jan 30 1991 |
Publication series
| Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|
Other
| Other | 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 |
|---|---|
| Country/Territory | United States |
| City | San Francisco |
| Period | 1/28/91 → 1/30/91 |
Bibliographical note
Funding Information:We improve upon the result in [Aga89] by construct-ing a structure for ray-shooting in an arrangement of possibly intersecting segments that achieves O(n log3 n) space and O(@ log n) query time. For non-intersecting segments, the space is improvable to O(n log2 n). The preprocessing time is the same as in [Aga89], namely, O(n@logW n), where w is a constant less than 4.3. As in [Aga89], our result also makes extensive use of spanning trees of low stabbing number. We also ex-tend the ray-shooting s~ructure to solve the general seg-ment intersection ~earching problem. Our algorithm uses O(n log3 n) space and reports in O(min{filog n + k log n, @ log2 n + k}) time the k intersections between a query segment and n possibly intersecting segments. The space can be improved to O(n log2 n) for non-intersecting segments. However, the query time will then increase slightly to O(fi log n + k log n). In [Aga89], an O(@ log2 n + k log n) query time is claimed for the case of a query ray and n non-intersecting segments, but the general problem is left open. Using a different method, Overmars et al. [0 SS89] construct O(n log n)-space and O(n~ log n + /c)-query time data structures for both non-intersecting and intersecting segments. “Department of Computer Science,University of Mhmesota,Minneapolis, MN 55455.Authors’ e-mail addresses:scheng(hurm-csc.a.umn.edu, janardantkmn-cs. cs.umn.edu. +T& resem&was supportedinpartbyagrant-in-aidofresearchfromtheGraduateSchOOl of the University of Minnesota. The secondauthor was also supported in part by NSF grant CCR-8808574.
Publisher Copyright:
© 1991 Association for Computing Machinery. All rights reserved.