An algorithm for generalized point location and its applications

Bernard Chazelle, Micha Sharir

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

We show that Collins' classical quantifier elimination procedure contains most of the ingredients for an efficient point location algorithm in higher-dimensional space. This leads to a polynomial-size data structure that allows us to locate, in logarithmic time, a point among a collection of real algebraic varieties of constant maximum degree, assuming that the dimension of the ambient space is fixed. This result has theoretical bearings on a number of optimization problems posed in the literature. It also gives a method for solving multidimensional searching problems in polynomial space and logarithmic query time.

Original languageEnglish (US)
Pages (from-to)281-309
Number of pages29
JournalJournal of Symbolic Computation
Volume10
Issue number3-4
DOIs
StatePublished - Jan 1 1990

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Computational Mathematics

Fingerprint Dive into the research topics of 'An algorithm for generalized point location and its applications'. Together they form a unique fingerprint.

Cite this