@inproceedings{11017e5018e24b7fbdbecca08d501f60,

title = "Searching in higher dimension",

abstract = "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.",

author = "Bernard Chazelle",

year = "1990",

month = jan,

day = "1",

doi = "10.1007/3-540-52921-7_64",

language = "English (US)",

isbn = "9783540529217",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

editor = "Toshihide lbaraki and Takao Nishizeki and Hiroshi Imai and Tetsuo Asano",

booktitle = "Algorithms - International Symposium SlGAL 1990, Proceedings",

address = "Germany",

note = "1st SIGAL International Symposium on Algorithms, 1990 ; Conference date: 16-08-1990 Through 18-08-1990",

}