Some techniques for geometric searching with implicit set representations

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


There are many efficient ways of searching a set when all its elements can be represented in memory. Often, however, the domain of the search is too large to have each element stored separately, and some implicit representation must be used. Whether it is still possible to search efficiently in these conditions is the underlying theme of this paper. We look at several occurrences of this problem in computational geometry and we propose various lines of attack. In the course of doing so, we improve the solutions of several specific problems; for example, computing order statistics, performing polygonal range searching, testing algebraic predicates, etc.

Original languageEnglish (US)
Pages (from-to)565-582
Number of pages18
JournalActa Informatica
Issue number5
StatePublished - Sep 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Some techniques for geometric searching with implicit set representations'. Together they form a unique fingerprint.

Cite this