ISSN:
1432-0541
Keywords:
Computational geometry
;
Ray-shooting
;
Triangulation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01377183
Permalink
