Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (Scopus)

Samenvatting

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+e) 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+e) storage and preprocessing time such that queries take O((n/vm)log2 n) 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 n <m <n3, we can construct a structure that uses O(m1+e) 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.
Originele taal-2Engels
TitelProceedings 22nd Annual ACM Symposium on Computational Geometry (SoCG'06, Sedona AR, USA, June 5-7, 2006)
RedacteurenN. Amenta, O. Cheong
Pagina's88-94
DOI's
StatusGepubliceerd - 2006

Vingerafdruk

Duik in de onderzoeksthema's van 'Ray shooting and intersection searching amidst fat convex polyhedra in 3-space'. Samen vormen ze een unieke vingerafdruk.

Citeer dit