Ray shooting in polygons using geodesic triangulations |
| |
| Authors: | B. Chazelle H. Edelsbrunner M. Grigni L. Guibas J. Hershberger M. Sharir J. Snoeyink |
| |
| Affiliation: | (1) Computer Science Department, Princeton University, 08544 Princeton, NJ, USA;(2) Computer Science Department, University of Illinois, 61801 Urbana, IL, USA;(3) Department of Mathematics, MIT, 02139 Cambridge, MA, USA;(4) DEC Systems Research Center, 130 Lytton Avenue, 94301 Palo Alto, CA, USA;(5) Laboratory for Computer Science, MIT, 02139 Cambridge, MA, USA;(6) Computer Science Department, Stanford University, 94305-4055 Stanford, CA, USA;(7) School of Mathematical Sciences, Tel Aviv University, 69 978 Ramat Aviv, Israel;(8) Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, 10012 New York, NY, USA |
| |
| Abstract: | LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO( logn) time.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. |
| |
| Keywords: | Computational geometry Ray-shooting Triangulation |
| 本文献已被 SpringerLink 等数据库收录！ |
|
