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

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

doi:10.1016/j.comgeo.2007.10.006

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

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

Algorithms

Research output: Contribution to journal › Article › Academic › peer-review

11 Citations (Scopus)

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(n2+e) storage and preprocessing time, and queries can be answered in O(log2n) time. A trade-off between storage and query time is also possible: for any m with n

Original language	English
Pages (from-to)	68-76
Journal	Computational Geometry
Volume	41
Issue number	1-2
DOIs	https://doi.org/10.1016/j.comgeo.2007.10.006
Publication status	Published - 2008

Access to Document

10.1016/j.comgeo.2007.10.006

Cite this

@article{54eb8544de69410396624a83612f49c0,

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 . The data structure uses O(n2+e) storage and preprocessing time, and queries can be answered in O(log2n) time. A trade-off between storage and query time is also possible: for any m with n",

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

year = "2008",

doi = "10.1016/j.comgeo.2007.10.006",

language = "English",

volume = "41",

pages = "68--76",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

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 - 2008

Y1 - 2008

N2 - 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(n2+e) storage and preprocessing time, and queries can be answered in O(log2n) time. A trade-off between storage and query time is also possible: for any m with n

AB - 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(n2+e) storage and preprocessing time, and queries can be answered in O(log2n) time. A trade-off between storage and query time is also possible: for any m with n

U2 - 10.1016/j.comgeo.2007.10.006

DO - 10.1016/j.comgeo.2007.10.006

M3 - Article

SN - 0925-7721

VL - 41

SP - 68

EP - 76

JO - Computational Geometry

JF - Computational Geometry

IS - 1-2

ER -

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

Abstract

Access to Document

Fingerprint

Cite this