Optimal and Near-Optimal Algorithms for Generalized Intersection Reporting on Pointer Machines

Simple item page
dc.contributor.authorShi, Qingminen_US
dc.contributor.authorJaJa, Josephen_US
dc.date.accessioned2004-05-31T23:34:05Z
dc.date.available2004-05-31T23:34:05Z
dc.date.created2003-11en_US
dc.date.issued2003-11-25en_US
dc.description.abstractWe develop efficient algorithms for a number of generalized intersection reporting problems, including orthogonal and general segment intersection, 2-D range searching, rectangular point enclosure, and rectangle intersection search. Our results for orthogonal and general segment intersection, 3-sided 2-D range searching, and rectangular pointer enclosure problems match the lower bounds for their corresponding standard versions under the pointer machine model. Our results for the remaining problems improve upon the best known previous algorithms. (UMIACS-TR-2003-110)en_US
dc.format.extent259548 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/1325
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4542en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-2003-110en_US
dc.titleOptimal and Near-Optimal Algorithms for Generalized Intersection Reporting on Pointer Machinesen_US
dc.typeTechnical Reporten_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
CS-TR-4542.pdf
Size:
253.46 KB
Format:
Adobe Portable Document Format
Download

Collections

Technical Reports from UMIACS
Technical Reports of the Computer Science Department