Ray shooting in polygons using geodesic triangulations

B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, J. Snoeyink, in:, Springer, 1991, pp. 661–673.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ; ; ; ; ;
Series Title
LNCS
Abstract
Let P be a simple polygon with n vertices. We present a simple decomposition scheme that partitions the interior of P into O(n) so-called geodesic triangles, so that any line segment interior to P crosses at most 2 log n of these triangles. This decomposition can be used to preprocess P in time O(n log n) and storage O(n), so that any ray-shooting query can be answered in time O(log n).The algorithms are fairly simple and easy to implement. We also extend this technique to the case of ray-shooting amidst k polygonal obstacles with a total of n edges, so that a query can be answered in O(radicklog n) time.
Publishing Year
Date Published
1991-06-20
Acknowledgement
NSF Grant CCR-89-21421
Volume
510
Page
661 - 673
Conference
ICALP: Automata, Languages and Programming
IST-REx-ID

Cite this

Chazelle B, Edelsbrunner H, Grigni M, et al. Ray shooting in polygons using geodesic triangulations. In: Vol 510. Springer; 1991:661-673. doi:10.1007/3-540-54233-7_172
Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Hershberger, J., Sharir, M., & Snoeyink, J. (1991). Ray shooting in polygons using geodesic triangulations (Vol. 510, pp. 661–673). Presented at the ICALP: Automata, Languages and Programming, Springer. https://doi.org/10.1007/3-540-54233-7_172
Chazelle, Bernard, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink. “Ray Shooting in Polygons Using Geodesic Triangulations,” 510:661–73. Springer, 1991. https://doi.org/10.1007/3-540-54233-7_172.
B. Chazelle et al., “Ray shooting in polygons using geodesic triangulations,” presented at the ICALP: Automata, Languages and Programming, 1991, vol. 510, pp. 661–673.
Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Hershberger J, Sharir M, Snoeyink J. 1991. Ray shooting in polygons using geodesic triangulations. ICALP: Automata, Languages and Programming, LNCS, vol. 510. 661–673.
Chazelle, Bernard, et al. Ray Shooting in Polygons Using Geodesic Triangulations. Vol. 510, Springer, 1991, pp. 661–73, doi:10.1007/3-540-54233-7_172.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar