Ray shooting in polygons using geodesic triangulations
Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Hershberger J, Sharir M, Snoeyink J. 1991. Ray shooting in polygons using geodesic triangulations. 18th International Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 510, 661–673.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
;
Grigni, Michelangelo;
Guibas, Leonidas;
Hershberger, John;
Sharir, Micha;
Snoeyink, Jack
;
Grigni, Michelangelo;
Guibas, Leonidas;
Hershberger, John;
Sharir, Micha;
Snoeyink, JackSeries 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
Proceedings Title
18th International Colloquium on Automata, Languages and Programming
Publisher
Springer
Acknowledgement
Work by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-89-21421. Work by Micha Sharir has been supported by ONR Grants N00014-89-J-3042 and N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.
Volume
510
Page
661 - 673
Conference
ICALP: Automata, Languages and Programming
Conference Location
Madrid, Spain
Conference Date
1991-07-08 – 1991-07-12
IST-REx-ID
Cite this
Chazelle B, Edelsbrunner H, Grigni M, et al. Ray shooting in polygons using geodesic triangulations. In: 18th International Colloquium on Automata, Languages and Programming. 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. In 18th International Colloquium on Automata, Languages and Programming (Vol. 510, pp. 661–673). Madrid, Spain: 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.” In 18th International Colloquium on Automata, Languages and Programming, 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,” in 18th International Colloquium on Automata, Languages and Programming, Madrid, Spain, 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. 18th International Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 510, 661–673.
Chazelle, Bernard, et al. “Ray Shooting in Polygons Using Geodesic Triangulations.” 18th International Colloquium on Automata, Languages and Programming, vol. 510, Springer, 1991, pp. 661–73, doi:10.1007/3-540-54233-7_172.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar