# MPI-I-93-124

## Algorithms for some intersection searching problems involving curved objects

### Gupta, Prosenjit and Janardan, Ravi and Smid, Michiel

**MPI-I-93-124**. June** **1993, 43 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

Three classes of geometric intersection searching problems are

considered, i.e., problems in which a set $S$ of geometric

objects is to be preprocessed into a data structure so

that for any query object $q$, the objects of $S$ that are

intersected by $q$ can be counted or reported efficiently.

In the first class, $S$ is a set of linear objects, such as lines

or line segments, and $q$ is a curved object, such as a circle,

disk, or circular arc. In the second class, $S$ is a set of

curved objects, such as $d$-balls, $d$-spheres, circles,

or circular arcs, and $q$ is also a curved object.

In the third class, which is a generalization of the first two,

the objects in $S$ are curved or linear and each is assigned

a color. Given a query $q$, such as a disk or an annulus,

the goal is to count or report the distinct colors of the

objects intersected by $q$.

Efficient solutions are presented for a wide variety of

problems from these classes. The solution techniques are based

on geometric transformations, on compositions of known solutions

for simplex range searching, on the locus approach,

and on persistent data structures. Previously, efficient solutions

for such curved intersection searching problems were known only

for the case where $S$ consists of curved objects and $q$ is linear.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-93-124.pdf | 76 KBytes; 242 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-124

**BibTeX**
`@TECHREPORT{``GuptaJanardanSmid93a``,`

` AUTHOR = {Gupta, Prosenjit and Janardan, Ravi and Smid, Michiel},`

` TITLE = {Algorithms for some intersection searching problems involving curved objects},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-93-124},`

` MONTH = {June},`

` YEAR = {1993},`

` ISSN = {0946-011X},`

`}`