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

Loading...
Thumbnail Image

Files

CS-TR-4542.pdf (253.46 KB)
No. of downloads: 707

Publication or External Link

Date

2003-11-25

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)

Notes

Rights