--- res: bibo_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.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Bernard foaf_name: Chazelle, Bernard foaf_surname: Chazelle - foaf_Person: foaf_givenName: Herbert foaf_name: Edelsbrunner, Herbert foaf_surname: Edelsbrunner foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-9823-6833 - foaf_Person: foaf_givenName: Michelangelo foaf_name: Grigni, Michelangelo foaf_surname: Grigni - foaf_Person: foaf_givenName: Leonidas foaf_name: Guibas, Leonidas foaf_surname: Guibas - foaf_Person: foaf_givenName: John foaf_name: Hershberger, John foaf_surname: Hershberger - foaf_Person: foaf_givenName: Micha foaf_name: Sharir, Micha foaf_surname: Sharir - foaf_Person: foaf_givenName: Jack foaf_name: Snoeyink, Jack foaf_surname: Snoeyink bibo_doi: 10.1007/BF01377183 bibo_issue: '1' bibo_volume: 12 dct_date: 1994^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/0178-4617 dct_language: eng dct_publisher: Springer@ dct_title: Ray shooting in polygons using geodesic triangulations@ ...