Ray shooting amidst fat convex polyhedra in 3-space

B. Aronov, M. Berg, de, C.M. Gray

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic


We present a data structure for ray-shooting queries in a set of disjoint convex fat polyhedra of total com- plexity n in R3. The data structure uses O(n2+") storage and preprocessing time, and queries can be answered in O(log2 n) time. A trade-off between stor- age 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/pm) log2 n) time.
Original languageEnglish
Title of host publicationAbstracts 22nd European Workshop on Computational Geometry (EWCG 2006, Delphi, Greece, March 27-29, 2006)
EditorsI. Emiris, M. Karavelas, L. Palios
Publication statusPublished - 2006


Dive into the research topics of 'Ray shooting amidst fat convex polyhedra in 3-space'. Together they form a unique fingerprint.

Cite this