Further results on generalized intersection searching problems: Counting, reporting, and dynamization

Prosenjit Gupta, Ravi Janardan, Michiel Smid

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

In a generalized intersection searching problem, a set, S, of colored geometric objects is to be preprocessed so that given some query object, q, the distinct colors of the objects intersected by q can be reported or counted efficiently. In the dynamic setting, colored objects can be inserted into or deleted from S. These problems generalize the well-studied standard intersection searching problems and are rich in applications. Unfortunately, the techniques known for the standard problems do not yield efficient solutions for the generalized problems. Moreover, previous work on generalized problems applies only to the reporting problems and that too mainly to the static case. In this paper, a uniform framework is presented to solve efficiently the counting/reporting/dynamic versions of a variety of generalized intersection searching problems, including: 1-, 2-, and 3-dimensional range searching, quadrant searching, and 2-dimensional point enclosure searching. Several other related results are also mentioned.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides
PublisherSpringer Verlag
Pages361-372
Number of pages12
ISBN (Print)9783540571551
DOIs
StatePublished - 1993
Event3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada
Duration: Aug 11 1993Aug 13 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume709 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Workshop on Algorithms and Data Structures, WADS 1993
CountryCanada
CityMontreal
Period8/11/938/13/93

Bibliographical note

Funding Information:
1Department of Computer Science, University of Minnesota, Minneapolis, MN 55455, U.S.A. Email: {pgupt a, j anardan}@cs, umn. edu. The research of these authors was supported in part by NSF grant CCR-92-00270.

Funding Information:
2Max-Planck-Institut fiLr Informatik, W-6600 Saarbrficken, Germany. Email: micMel@mpi-sb.mpg.de. This author was supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM II).

Keywords

  • Computational geometry
  • Data structures
  • Dynamization
  • Intersection searching
  • Persistence

Fingerprint Dive into the research topics of 'Further results on generalized intersection searching problems: Counting, reporting, and dynamization'. Together they form a unique fingerprint.

Cite this