### 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.

Original language | English (US) |
---|---|

Title of host publication | Algorithms - International Symposium SlGAL 1990, Proceedings |

Editors | Toshihide lbaraki, Takao Nishizeki, Hiroshi Imai, Tetsuo Asano |

Publisher | Springer Verlag |

ISBN (Print) | 9783540529217 |

DOIs | |

State | Published - Jan 1 1990 |

Event | 1st SIGAL International Symposium on Algorithms, 1990 - Tokyo, Japan Duration: Aug 16 1990 → Aug 18 1990 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 450 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 1st SIGAL International Symposium on Algorithms, 1990 |
---|---|

Country | Japan |

City | Tokyo |

Period | 8/16/90 → 8/18/90 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

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

## Cite this

*Algorithms - International Symposium SlGAL 1990, Proceedings*(Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 450 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-52921-7_64