TY - JOUR
T1 - Ray shooting and intersection searching amidst fat convex polyhedra in 3-space
AU - Aronov, Boris
AU - De Berg, Mark
AU - Gray, Chris
N1 - Funding Information:
* Corresponding author. E-mail addresses: [email protected] (M. de Berg), [email protected] (C. Gray). URL: http://cis.poly.edu/~aronov. 1 Research supported in part by NSF grant ITR-0081964 and by a grant from the US–Israel Binational Science Foundation. Part of the research was performed when B.A. visited TU Eindhoven in June 2005. 2 Research supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.
PY - 2008/10
Y1 - 2008/10
N2 - We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in R3. The data structure uses O(n2 +) storage and preprocessing time, and queries can be answered in O( log2n) time. A trade-off between storage and query time is also possible: for any m with nn2, we can construct a structure that uses O(m1 +) storage and preprocessing time such that queries take O((n/m) log2n) time. We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in R3. For any m with nn3, we can construct a structure that uses O(m1 +) storage and preprocessing time such that all polyhedra intersecting a query simplex can be reported in O((n/m1 /3)logn+k) time, where k is the number of answers.
AB - We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in R3. The data structure uses O(n2 +) storage and preprocessing time, and queries can be answered in O( log2n) time. A trade-off between storage and query time is also possible: for any m with nn2, we can construct a structure that uses O(m1 +) storage and preprocessing time such that queries take O((n/m) log2n) time. We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in R3. For any m with nn3, we can construct a structure that uses O(m1 +) storage and preprocessing time such that all polyhedra intersecting a query simplex can be reported in O((n/m1 /3)logn+k) time, where k is the number of answers.
KW - Fat objects
KW - Geometric data structures
KW - Intersection searching
KW - Ray shooting
UR - http://www.scopus.com/inward/record.url?scp=84867992862&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867992862&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2007.10.006
DO - 10.1016/j.comgeo.2007.10.006
M3 - Article
AN - SCOPUS:84867992862
SN - 0925-7721
VL - 41
SP - 68
EP - 76
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 1-2
ER -