Ray shooting in polygons using geodesic triangulations

B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, J. Snoeyink, Algorithmica 12 (1994) 54–68.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ; ; ; ;
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 a very simple manner, so that any ray-shooting query can be answered in time O(log n). The data structure requires O(n) storage and O(n log n) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time to O(n). We also extend our general 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(√ log n) time.
Publishing Year
Date Published
1994-07-01
Journal Title
Algorithmica
Acknowledgement
NSF Grant CCR-89-21421
Volume
12
Issue
1
Page
54 - 68
IST-REx-ID

Cite this

Chazelle B, Edelsbrunner H, Grigni M, et al. Ray shooting in polygons using geodesic triangulations. Algorithmica. 1994;12(1):54-68. doi:10.1007/BF01377183
Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Hershberger, J., Sharir, M., & Snoeyink, J. (1994). Ray shooting in polygons using geodesic triangulations. Algorithmica, 12(1), 54–68. https://doi.org/10.1007/BF01377183
Chazelle, Bernard, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink. “Ray Shooting in Polygons Using Geodesic Triangulations.” Algorithmica 12, no. 1 (1994): 54–68. https://doi.org/10.1007/BF01377183.
B. Chazelle et al., “Ray shooting in polygons using geodesic triangulations,” Algorithmica, vol. 12, no. 1, pp. 54–68, 1994.
Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Hershberger J, Sharir M, Snoeyink J. 1994. Ray shooting in polygons using geodesic triangulations. Algorithmica. 12(1), 54–68.
Chazelle, Bernard, et al. “Ray Shooting in Polygons Using Geodesic Triangulations.” Algorithmica, vol. 12, no. 1, Springer, 1994, pp. 54–68, doi:10.1007/BF01377183.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar