TY - JOUR
T1 - Point location among hyperplanes and unidirectional ray-shooting
AU - Chazelle, Bernard
AU - Friedman, Joel
N1 - Funding Information:
*Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grants CCR-8700917 and CCR-9002352. Joel Friedman wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8858788, and the Office of Naval Research under Grant N00014-87-K-0467. * Corresponding author.
PY - 1994/6
Y1 - 1994/6
N2 - We present an algorithm for locating a query point q in an arrangement of n hyperplanes in Rd. The size of the data structure is O(nd) and the time to answer any query is O(logn). Unlike previous data structures, our solution will also report, in addition to the face of the arrangement that contains q, the first hyperplane that is hit (if any) by shooting the point q in some fixed direction. Actually, if this ray-shooting capability is all that is needed, or if one only desires to know a single vertex of the face enclosing q, then the storage can be reduced to O(nd/(logn)⌈d/2⌉-ε{lunate}), for any fixed ε{lunate} >0.
AB - We present an algorithm for locating a query point q in an arrangement of n hyperplanes in Rd. The size of the data structure is O(nd) and the time to answer any query is O(logn). Unlike previous data structures, our solution will also report, in addition to the face of the arrangement that contains q, the first hyperplane that is hit (if any) by shooting the point q in some fixed direction. Actually, if this ray-shooting capability is all that is needed, or if one only desires to know a single vertex of the face enclosing q, then the storage can be reduced to O(nd/(logn)⌈d/2⌉-ε{lunate}), for any fixed ε{lunate} >0.
KW - Multidimensional searching
KW - Point location
KW - Ray-shooting
UR - http://www.scopus.com/inward/record.url?scp=38149147604&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38149147604&partnerID=8YFLogxK
U2 - 10.1016/0925-7721(94)90009-4
DO - 10.1016/0925-7721(94)90009-4
M3 - Article
AN - SCOPUS:38149147604
SN - 0925-7721
VL - 4
SP - 53
EP - 62
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 2
ER -