A technique for adding range restrictions to generalized searching problems

✍ Scribed by Prosenjit Gupta; Ravi Janardan; Michiel Smid

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 681 KB
• Volume: 64
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00183-x

✦ Synopsis

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 S 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 0( n'+' ) and query time O( (logn)' + C). Here, C denotes the number of colors reported by the query, and E is an arbitrarily small positive constant. @