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

Boris Aronov; Mark De Berg; Chris Gray

doi:10.1145/1137856.1137872

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

Boris Aronov, Mark De Berg, Chris Gray

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in ℝ³. The data structure uses O(n^2+ε) storage and preprocessing time, and queries can be answered in O(log² n) time. A trade-off between storage and query time is also possible: for any m with n < m < n², we can construct a structure that uses O(m^1+ε) storage and preprocessing time such that queries take O((n/√m) log² n) time. We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in ℝ³. For any m with n< m < n², we can construct a structure that uses O(m^1+ε) storage and preprocessing time such that all polyhedra intersecting a query simplex can be reported in O((n/m^1/3) log n + k) time, where k is the number of answers.

Original language	English (US)
Title of host publication	Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
Publisher	Association for Computing Machinery (ACM)
Pages	88-94
Number of pages	7
ISBN (Print)	1595933409, 9781595933409
DOIs	https://doi.org/10.1145/1137856.1137872
State	Published - 2006
Event	22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States Duration: Jun 5 2006 → Jun 7 2006

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry
Volume	2006

Other

Other	22nd Annual Symposium on Computational Geometry 2006, SCG'06
Country/Territory	United States
City	Sedona, AZ
Period	6/5/06 → 6/7/06

Keywords

Computational geometry
Fat objects
Intersection searching
Ray shooting

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/1137856.1137872

Cite this

Aronov, B., De Berg, M., & Gray, C. (2006). Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06 (pp. 88-94). (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1137856.1137872

Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. / Aronov, Boris; De Berg, Mark; Gray, Chris.
Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery (ACM), 2006. p. 88-94 (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aronov, B, De Berg, M & Gray, C 2006, Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. in Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Proceedings of the Annual Symposium on Computational Geometry, vol. 2006, Association for Computing Machinery (ACM), pp. 88-94, 22nd Annual Symposium on Computational Geometry 2006, SCG'06, Sedona, AZ, United States, 6/5/06. https://doi.org/10.1145/1137856.1137872

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

}

TY - GEN

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

AU - Aronov, Boris

AU - De Berg, Mark

AU - Gray, Chris

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

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

KW - Computational geometry

KW - Fat objects

KW - Intersection searching

KW - Ray shooting

UR - http://www.scopus.com/inward/record.url?scp=33748081122&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748081122&partnerID=8YFLogxK

U2 - 10.1145/1137856.1137872

DO - 10.1145/1137856.1137872

M3 - Conference contribution

AN - SCOPUS:33748081122

SN - 1595933409

SN - 9781595933409

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 88

EP - 94

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

PB - Association for Computing Machinery (ACM)

T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06

Y2 - 5 June 2006 through 7 June 2006

ER -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this