On intersection searching problems involving curved objects

Prosenjit Gupta, Ravi Janardan, Michiel Smid

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

6 Scopus citations


Efficient solutions are given for the problem of preprocessing a set of linear or curved geometric objects (e.g. lines, llne segments, circles, circular arcs, d-balls, d-spheres)such that the ones that are intersected by a curved query object can be reported (or counted) quickly. The problem is considered both in the standard setting (where one is interested in all the objects intersected) and in a generalized setting (where the input objects come aggregated in disjoint groups and one is interested in the disjoint groups that axe intersected). The solutions axe based on geometric transformations, simplex compositions, persistence, and, for the generalized problem, oa a method to progressively eliminate groups that cannot possibly be intersected.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsErik M. Schmidt, Sven Skyum
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540582182
StatePublished - 1994
Event4th Scandinavian Workshop on Algorithm Theory, SWAT 1994 - Aarhus, Denmark
Duration: Jul 6 1994Jul 8 1994

Publication series

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


Other4th Scandinavian Workshop on Algorithm Theory, SWAT 1994

Bibliographical note

Funding Information:
2Max-Planck-Institut ffw Informatik, D-66123 Saarbr~cken, Germany. Email: -ichielQmpi-sb .rups.de. This author w, m supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM II).

Funding Information:
Most previous work on these problems assumes that the input objects and the query object are linear or piecewise-linear. To our knowledge, the case where the input and/or the query are curved has been investigated systematically only. in \[AvKO93, KOA90, Sha91, AM92\]. In \[AvKO93\]s, earching on curved objects (e.g., circles, disks, circular arcs, Jordan arcs) with linear query objects (e.g., lines, line segments, halfspaces, rays) is considered. In \[KOAg0\]( resp. \[Sha91\]), the input is a set of disks and the query is a line or line segment (resp. a point), 1Department of Computer Science, Universlty'of Minnesota, Minneapolis, MN 55455, U.S.A. Enudl: {pgupta, j amardan)@cs,u am.e du. The research of these authors was supported in part by NSF grant CCR-92-00270.

Publisher Copyright:
© 1994, Springer Verlag. All rights reserved.


Dive into the research topics of 'On intersection searching problems involving curved objects'. Together they form a unique fingerprint.

Cite this