Point location among hyperplanes and unidirectional ray-shooting

Bernard Chazelle, Joel Friedman

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)53-62
Number of pages10
JournalComputational Geometry: Theory and Applications
Issue number2
StatePublished - Jun 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • Multidimensional searching
  • Point location
  • Ray-shooting


Dive into the research topics of 'Point location among hyperplanes and unidirectional ray-shooting'. Together they form a unique fingerprint.

Cite this