---
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 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Bernard
foaf_name: Chazelle, Bernard
foaf_surname: Chazelle
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
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/3-540-54233-7_172
bibo_volume: 510
dct_date: 1991^xs_gYear
dct_publisher: Springer@
dct_title: Ray shooting in polygons using geodesic triangulations@
...