Optimal and Near-Optimal Algorithms for Generalized Intersection Reporting on Pointer Machines
Optimal and Near-Optimal Algorithms for Generalized Intersection Reporting on Pointer Machines
Files
Publication or External Link
Date
2003-11-25
Authors
Advisor
Citation
DRUM DOI
Abstract
We 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)