Searching in higher dimension

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Multidimensional searching addresses search problems where the underlying universe lacks a total order. Hit detection in computer graphics, range searching in databases, point location in geographical maps are well-known instances of such problems. We will review some recent developments in that area. Point location in a nonlinear universe involves preprocessing a collection of real-algebraic varieties to facilitate the location of a query point. By using probabilistic data structuring techniques we can reduce the problem to the general question of stratifying semi-algebraic sets into simple smooth manifolds. Another subject of current interest is the manipulation of lines and segments in Euclidean 3-space. Given a set of lines one may wish to compute their upper envelope or be ready to answer questions of the form: given a new line (or a set of new lines), does it (or do they) all lie above the lines in the database? This problem has applications to ray-tracing in a polyhedral environment. Another subject with interesting recent developments is polytope range searching: the problem involves preprocessing a collection of points in rf-space so that, given a query simplex q, the number of points inside q can be evaluated efficiently. We wil report on practical solutions which offer a whole spectrum of quasi-optimal tradeoffs between storage and query time.

Original languageEnglish (US)
Title of host publicationAlgorithms - International Symposium SlGAL 1990, Proceedings
EditorsToshihide lbaraki, Takao Nishizeki, Hiroshi Imai, Tetsuo Asano
PublisherSpringer Verlag
ISBN (Print)9783540529217
StatePublished - 1990
Externally publishedYes
Event1st SIGAL International Symposium on Algorithms, 1990 - Tokyo, Japan
Duration: Aug 16 1990Aug 18 1990

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume450 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other1st SIGAL International Symposium on Algorithms, 1990

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Searching in higher dimension'. Together they form a unique fingerprint.

Cite this