Point location among hyperplanes and unidirectional ray-shooting

Bernard Chazelle, Joel Friedman

Research output: Contribution to journalArticle

16 Scopus citations

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.

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

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

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

  • Cite this