Abstract
In a generalized searching problem, a set S of n colored geometric objects has to be stored in a data structure, such that for any given query object q, the distinct colors of the objects of 5 intersected by q can be reported efficiently. In this paper, a general technique is presented for adding a range restriction to such a problem. The technique is applied to the problem of querying a set of colored points (respectively fat triangles) with a fat triangle (respectively point). For both problems, a data structure is obtained having size O(n1+ε) and query time O((log n)2 + C). Here, C denotes the number of colors reported by the query, and ε is an arbitrarily small positive constant.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 263-269 |
| Number of pages | 7 |
| Journal | Information Processing Letters |
| Volume | 64 |
| Issue number | 5 |
| DOIs | |
| State | Published - Dec 15 1997 |
Bibliographical note
Funding Information:* Corresponding author. Email: janardan@cs.umn.edu. This author was supported by a Grant-in-Aid of Research from the Graduate School of the University of Minnesota. 1E mail: prosenjit@lucent.com. Part of this work was done while at MPI-Informatik, Saarbrticken, Germany. ’ Email: michiel@isg.cs.uni-magdeburgde. Part of this work was done while at MPI-Informatik, Saarbrticken, Germany, and the Department of Computer Science, King’s College London, UK.
Keywords
- Computational geometry
- Data structures
- Intersection searching
- Range restriction