Efficient non-intersection queries on aggregated geometric data

Prosenjit Gupta, Ravi Janardan, Michiel Smid

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


Let S be a set of geometric objects that are aggregated into disjoint groups. The problem considered is that of preprocessing S so that for any query object, q, the distinct groups such that no objects from those groups are intersected by q can be reported efficiently. The goal is to devise solutions where the query time is sensitive to the output size, i.e., the number of groups reported. Unfortunately, the obvious approaches of (i) solving the corresponding intersection problem for aggregated data and reporting the complement, or (ii) querying with the complement of q are either expensive or incorrect. Efficient, output-sensitive solutions are given to several non-intersection searching problems on aggregated data, using methods such as geometric duality, sparsification, persistence, filtering search, and pruning.

Original languageEnglish (US)
Pages (from-to)544-553
Number of pages10
JournalLecture Notes in Computer Science
StatePublished - Oct 24 2005
Externally publishedYes
Event11th Annual International Conference on Computing and Combinatorics, COCOON 2005 - Kunming, China
Duration: Aug 16 2005Aug 29 2005


Dive into the research topics of 'Efficient non-intersection queries on aggregated geometric data'. Together they form a unique fingerprint.

Cite this