English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  A technique for adding range restrictions to generalized searching problems

Gupta, P., Janardan, R., & Smid, M.(1996). A technique for adding range restrictions to generalized searching problems (MPI-I-1996-1-017). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Files

show Files
hide Files
:
MPI-I-96-1-017.pdf (Any fulltext), 190KB
Name:
MPI-I-96-1-017.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Gupta, Prosenjit1, Author           
Janardan, Ravi2, Author
Smid, Michiel1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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 $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 (resp.\ fat triangles) with a fat triangle (resp.\ point). For both problems, a data structure is obtained having size $O(n^{1+\epsilon})$ and query time $O((\log n)^2 + C)$. Here, $C$ denotes the number of colors reported by the query, and $\epsilon$ is an arbitrarily small positive constant.

Details

show
hide
Language(s): eng - English
 Dates: 1996
 Publication Status: Issued
 Pages: 9 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: MPI-I-1996-1-017
BibTex Citekey: GuptaJanardanSmid96b
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -