Abstract
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 language | English |
---|---|
Title of host publication | Abstracts 22nd European Workshop on Computational Geometry (EWCG 2006, Delphi, Greece, March 27-29, 2006) |
Editors | I. Emiris, M. Karavelas, L. Palios |
Pages | 21-24 |
Publication status | Published - 2006 |