Point location among hyperplanes and unidirectional ray-shooting

Bernard Chazelle; Joel Friedman

doi:10.1016/0925-7721(94)90009-4

Point location among hyperplanes and unidirectional ray-shooting

Bernard Chazelle
, Joel Friedman

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

22 Scopus citations

Abstract

We present an algorithm for locating a query point q in an arrangement of n hyperplanes in R^d. The size of the data structure is O(n^d) 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(n^d/(logn)^{⌈d/2⌉-ε{lunate}}), for any fixed ε{lunate} >0.

Original language	English (US)
Pages (from-to)	53-62
Number of pages	10
Journal	Computational Geometry: Theory and Applications
Volume	4
Issue number	2
DOIs	https://doi.org/10.1016/0925-7721(94)90009-4
State	Published - Jun 1994
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Keywords

Multidimensional searching
Point location
Ray-shooting

Access to Document

10.1016/0925-7721(94)90009-4

Cite this

@article{adab6bb29c13485ea6e6cab6849e4261,

title = "Point location among hyperplanes and unidirectional ray-shooting",

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

keywords = "Multidimensional searching, Point location, Ray-shooting",

author = "Bernard Chazelle and Joel Friedman",

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

year = "1994",

month = jun,

doi = "10.1016/0925-7721(94)90009-4",

language = "English (US)",

volume = "4",

pages = "53--62",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "2",

}

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 - https://www.scopus.com/pages/publications/38149147604

UR - https://www.scopus.com/pages/publications/38149147604#tab=citedBy

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 -

Point location among hyperplanes and unidirectional ray-shooting

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this