Ray Shooting Amidst Convex Polygons in 2D |
| |
Authors: | Pankaj K Agarwal Micha Sharir |
| |
Institution: | aDepartment of Computer Science, Duke University, Box 90129, Durham, North Carolina, 27708-0129;bSchool of Mathematics, Tel Aviv University, Tel Aviv, 69978, Israel;cCourant Institute of Mathematical Sciences, New York University, New York, New York, 10012 |
| |
Abstract: | We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log2 m log2 n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m2+n)log m) andO((m2+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/formula]1+ log2 n) time, for any >0. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|