TY - GEN
T1 - Searching in higher dimension
AU - Chazelle, Bernard
N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1990.
PY - 1990
Y1 - 1990
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85031781132
UR - https://www.scopus.com/pages/publications/85031781132#tab=citedBy
U2 - 10.1007/3-540-52921-7_64
DO - 10.1007/3-540-52921-7_64
M3 - Conference contribution
SN - 9783540529217
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
BT - Algorithms - International Symposium SlGAL 1990, Proceedings
A2 - lbaraki, Toshihide
A2 - Nishizeki, Takao
A2 - Imai, Hiroshi
A2 - Asano, Tetsuo
PB - Springer Verlag
T2 - 1st SIGAL International Symposium on Algorithms, 1990
Y2 - 16 August 1990 through 18 August 1990
ER -