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.
Bibliographical noteFunding Information:
* Corresponding author. Email: firstname.lastname@example.org. This author was supported by a Grant-in-Aid of Research from the Graduate School of the University of Minnesota. 1E mail: email@example.com. Part of this work was done while at MPI-Informatik, Saarbrticken, Germany. ’ Email: firstname.lastname@example.org. Part of this work was done while at MPI-Informatik, Saarbrticken, Germany, and the Department of Computer Science, King’s College London, UK.
- Computational geometry
- Data structures
- Intersection searching
- Range restriction