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

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

doi:10.1145/1137856.1137872

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

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proceedings 22nd Annual ACM Symposium on Computational Geometry (SoCG'06, Sedona AR, USA, June 5-7, 2006)
Editors	N. Amenta, O. Cheong
Pages	88-94
DOIs	https://doi.org/10.1145/1137856.1137872
Publication status	Published - 2006

Access to Document

10.1145/1137856.1137872

Cite this

@inproceedings{696aa03244c54e54b0e216f4d38a1b1d,

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 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.",

author = "B. Aronov and {Berg, de}, M. and C.M. Gray",

year = "2006",

doi = "10.1145/1137856.1137872",

language = "English",

pages = "88--94",

editor = "N. Amenta and O. Cheong",

booktitle = "Proceedings 22nd Annual ACM Symposium on Computational Geometry (SoCG'06, Sedona AR, USA, June 5-7, 2006)",

}

Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. / Aronov, B.; Berg, de, M.; Gray, C.M.

Proceedings 22nd Annual ACM Symposium on Computational Geometry (SoCG'06, Sedona AR, USA, June 5-7, 2006). ed. / N. Amenta; O. Cheong. 2006. p. 88-94.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Aronov, B.

AU - Berg, de, M.

AU - Gray, C.M.

PY - 2006

Y1 - 2006

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+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.

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+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.

U2 - 10.1145/1137856.1137872

DO - 10.1145/1137856.1137872

M3 - Conference contribution

SP - 88

EP - 94

BT - Proceedings 22nd Annual ACM Symposium on Computational Geometry (SoCG'06, Sedona AR, USA, June 5-7, 2006)

A2 - Amenta, N.

A2 - Cheong, O.

ER -

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

Abstract

Access to Document

Fingerprint

Cite this