@inproceedings{f83228c6601947829b3a3c3027c37a96,

title = "Ray shooting and intersection searching amidst fat convex polyhedra in 3-space",

abstract = "We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in ℝ3. The data structure uses O(n2+ε) storage and preprocessing time, and queries can be answered in O(log2 n) time. A trade-off between storage and query time is also possible: for any m with n < m < n2, we can construct a structure that uses O(m1+ε) storage and preprocessing time such that queries take O((n/√m) log2 n) time. We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in ℝ3. For any m with n< m < n2, 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) log n + k) time, where k is the number of answers.",

keywords = "Computational geometry, Fat objects, Intersection searching, Ray shooting",

author = "Boris Aronov and {De Berg}, Mark and Chris Gray",

year = "2006",

doi = "10.1145/1137856.1137872",

language = "English (US)",

isbn = "1595933409",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Association for Computing Machinery (ACM)",

pages = "88--94",

booktitle = "Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06",

address = "United States",

note = "22nd Annual Symposium on Computational Geometry 2006, SCG'06 ; Conference date: 05-06-2006 Through 07-06-2006",

}