de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Algorithms for some intersection searching problems involving curved objects

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44551

Gupta,  Prosenjit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-93-124.pdf
(beliebiger Volltext), 242KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Gupta, P., Janardan, R., & Smid, M.(1993). Algorithms for some intersection searching problems involving curved objects (MPI-I-93-124). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B3FC-B
Zusammenfassung
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.