×

Polygonal intersection searching. (English) Zbl 0486.68051


MSC:

68P10 Searching and sorting
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bentley, J. L., Multidimensional divide-and-conquer, Comm. ACM, 23, 214-229 (1980) · Zbl 0434.68049
[2] Bentley, J. L.; Maurer, H. A., Efficient worst-case data structures for range searching, Acta Inform., 13, 155-168 (1980) · Zbl 0423.68029
[3] Bentley, J. L.; Ottmann, Th., Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput., 28, 643-647 (1979) · Zbl 0414.68074
[4] Bentley, J. L.; Wood, D., An optimal worst-case algorithm for reporting intersections on rectangles, IEEE Trans. Comput., 29, 571-577 (1980)
[5] Brown, K. Q., Geometric transforms for fast geometric algorithms, (Report CMU-CS-80-10 (1980), Carnegie-Mellon University, Department of Computer Science)
[6] Brown, K. Q., Comments on ‘Algorithms for reporting and counting geometric intersections’, IEEE Trans. Comput., 30, 147-148 (1981) · Zbl 0447.68120
[7] Dobkin, D. P.; Lipton, R. J., Multidimensional searching problems, SIAM J. Comput., 5, 181-186 (1976) · Zbl 0333.68031
[8] Edelsbrunner, H., Dynamic rectangle intersection searching, (Report F47 (1980), Technical University of Graz, Institut für Informationsverarbeitung)
[9] Edelsbrunner, H., A time and space-optimal solution for the planar all intersecting rectangle problem, (Report 50 (1980), Technical University of Graz, Institut für Informationsverarbeitung)
[10] Edelsbrunner, H., Dynamic data structures for orthogonal intersection queries, (Report F59 (1980), Technical University of Graz, Institut für Informationsverarbeitung)
[11] Edelsbrunner, H.; Maurer, H. A., A space-optimal solution of general region location, Theoret. Comput. Sci., 16, 329-336 (1981) · Zbl 0468.68075
[12] Edelsbrunner, H.; Maurer, H. A., On the intersection of orthogonal objects, (Report F60 (1980), Technical University of Graz, Institut für Informationsverarbeitung) · Zbl 0583.90023
[13] Kirkpatrick, D. G., Optimal search in planar subdivisions (1979), University of British Columbia, Department of Computer Science, manuscript
[14] Nievergelt, J.; Preparata, F. P., Plane sweep algorithms for intersecting geometric figures, (Report R-863 (1979), University of Illinois at Urbana-Champaign, Coordinated Science Laboratory) · Zbl 0491.68075
[15] Preparata, F. P., A new approach to planar point location, (Report R-829 (1978), University of Illinois at Urbana-Champaign, Coordinated Science Laboratory) · Zbl 0421.68046
[16] Shamos, M. I.; Hoey, D., Geometric intersection problems, Proc. 17th Annual Symposium on Foundations of Computer Science, 208-215 (1976)
[17] Six, H.-W.; Wood, D., The rectangle intersection problem revisited, BIT, 20, 426-433 (1980)
[18] Six, H.-W.; Wood, D., Counting and reporting intersections of d-ranges, (Report 80-CS-6 (1980), McMaster University, Unit for Computer Science) · Zbl 0477.68072
[19] Vaishnavi, V. K., Computing point enclosures (1980), Concordia University, Computer Science Department, manuscript
[20] Vaishnavi, V. K.; Wood, D., Rectilinear line segment intersection, layered segment trees and dynamization, (Report 80-CS-8 (1980), McMaster University, Unit for Computer Science) · Zbl 0481.68062
[21] Willard, D. E., New data structures for orthogonal queries, (Report TR-22-78 (1978), Harvard University, Aiken Computer Laboratory) · Zbl 0564.68071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.