---
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@
...