From: ted@cs.umn.edu (Ted Stockwell)
Newsgroups: comp.theory
Subject: SUMMARY: multidimensional range searching
Date: 22 Aug 92 15:57:09 GMT
Organization: Midwest Software Journeymen


Below are the (slightly edited) responses I received to my request for
information on multidimensional range searching.  Thanks to everyone
who replied!

> From: dev@cs.brown.edu (Darren Erik Vengroff)
> Organization: Brown University Department of Computer Science
> 
> Samet has written a pair of books that cover the area quite well.
> They are
> 
> %A Hanan Samet
> %T The Design and Analysis of Spatial Data Structures
> %I Addison-Wesley
> %D 1989
> 
> %A Hanan Samet
> %T Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS
> %I Addison-Wesley
> %D 1989
> 
> If what you are looking for is not in one of these books it is sure
> to be in one of the several hundred entries in the bibliography.
> 
> -Darren
> 
> 
> From: Peter Su <psu@cs.duke.edu>
> Status: OR
> 
> Look in Preperata and Shamos: _Computational Geometry_ and also a book
> by Samet _Spatial data structures_ for a good overview.
> 
> Oh, also, Kurt Melhorn has a 3 vol. set of algorithms books, and the
> third volume covers multi-dimensional searching.
> 
> There is a lot of heavy theory in Melhorn and P&S...Samet is more
> application oriented- spatial databases and what not.
> 
> 
> From: salzberg@corwin.ccs.northeastern.edu (betty j salzberg)
> 
> an article Dave Lomet wrote will appear in the next sigmod record. IT
> is about multiattribute range searching. It is short and has good
> insights.
> 
> 
> From: rbaeza@dcc.uchile.cl (Ricardo Baeza)
> For a complete set of references on the topic, check
> "Handbook of Algorithms and Data Structures", Addison-Wesley, 2nd edition,
> 1991 by Gonnet and myself.
> 
> 
> From: enni@imada.ou.dk (Steffen Zacho Enni)
> 
> I have been looking for the same things. And the best I have found
> is Bentleys article in CACM 1975 (page 517-29, I think).
> 
> In this article he introduces the k-d tree and some algorithms
> There is an algorithm to range searching.
> 
> In another article by Bentley, Friedmann and Finkel ( "An Algorithm
> for Finding Best Matches in Logarithmic Expected Time" by
> J.H.Friedman, J.L.Bentley and R.A.Finkel. And it appeared in ACM
> Transactions on Mathematical Software, Vol. 3, No. 3, September 1977,
> Pages 209-226.) they present a slight variation of the k-d tree with
> an algorithm to finding nearest neighbors with every distance function
> you may wish. It runs in O(lg n) with O(nlgn) building time.
> 
> Shamos in his Introduction to computational Geometry also 
> contain some information about this subject, but it is
> presented in a more general way.
> 
> 
> From: aronov@ziggy.poly.edu (Boris Aronov)
> 
> This is all I could find in the computational geometry data base under
> range queries. Most of them ARE multidimensional (in the sense of not
> being 1-dimensional), but the types of queries varies very widely.
> 
> Hope this helps...
> 
>         40 matches found.
> 
> @inproceedings{am-rsps-92
> , author =      "P. K. Agarwal and J. Matou{\v s}ek"
> , title =       "Ray shooting and parametric search"
> , booktitle =   "Proc. 24th Annu. ACM Sympos. Theory Comput."
> , year =        "1992"
> , pages =       "??-??"
> , keywords =    "ray tracing, range search, intersection, partition trees"
> , comments =    "To appear"
> , oldlabel =    "geom-2481"
> }
> 
> @inproceedings{as-anps-91
> , author =      "P. K. Agarwal and M. Sharir"
> , title =       "Applications of a new partitioning scheme"
> , booktitle =   "Proc. 2nd Workshop Algorithms Data Struct."
> , series =      "Lecture Notes in Computer Science"
> , volume =      "519"
> , publisher =   "Springer-Verlag"
> , year =        "1991"
> , pages =       "379--391"
> , keywords =    "random sampling, range searching, ray tracing, hidden line/surface elimination"
> , oldlabel =    "geom-2625"
> }
> 
> @inproceedings{avo-iqco-91
> , author =      "P. K. Agarwal and M. van~Kreveld and M. Overmars"
> , title =       "Intersection queries for curved objects"
> , booktitle =   "Proc. 7th Annu. ACM Sympos. Comput. Geom."
> , year =        "1991"
> , pages =       "41--50"
> , keywords =    "range searching, partition trees, intersection"
> , oldlabel =    "geom-2572"
> }
> 
> @incollection{aeiim-pubtc-85
> , author =      "Ta. Asano and M. Edahiro and H. Imai and M. Iri and K. Murota"
> , title =       "Practical use of bucketing techniques in computational geometry"
> , editor =      "G. T. Toussaint"
> , booktitle =   "Computational Geometry"
> , publisher =   "North-Holland"
> , address =     "Amsterdam, Netherlands"
> , year =        "1985"
> , pages =       "153--195"
> , keywords =    "survey paper, implementing algorithms, optimization, bucketing, matchings, Voronoi diagrams, range search, point location, quad trees"
> , oldlabel =    "geom-1024"
> }
> 
> @article{acg-cdctd-89
> , author =      "M. J. Atallah and R. Cole and M. T. Goodrich"
> , title =       "Cascading divide-and-conquer:  {A} technique for designing parallel algorithms"
> , journal =     "SIAM J. Comput."
> , volume =      "18"
> , year =        "1989"
> , pages =       "499--532"
> , keywords =    "parallel computation, decomposition, range search, point location, visibility, domination, points, lines, divide-and-conquer, two-dimensional"
> , oldlabel =    "geom-901.2"
> }
> 
> @inproceedings{ag-epsp-86
> , author =      "M. J. Atallah and M. T. Goodrich"
> , title =       "Efficient plane sweeping in parallel"
> , booktitle =   "Proc. 2nd Annu. ACM Sympos. Comput. Geom."
> , year =        "1986"
> , pages =       "216--225"
> , keywords =    "parallel computation, decomposition, range search, point location, triangulation, visibility, domination, points, lines, two-dimensional"
> , oldlabel =    "geom-820"
> }
> 
> @inproceedings{as-ddsrs-81
> , author =      "Z. Aviad and E. Shamir"
> , title =       "A direct dynamic solution to range search and related problems for product regions"
> , booktitle =   "Proc. 22nd Annu. IEEE Sympos. Found. Comput. Sci."
> , year =        "1981"
> , pages =       "123--126"
> , keywords =    "orthogonal range queries, integer coordinates, multidimensional search"
> , oldlabel =    "geom-21"
> }
> 
> @article{a-npps-84
> , author =      "D. Avis"
> , title =       "Non-partitionable point sets"
> , journal =     "Inform. Process. Lett."
> , volume =      "19"
> , year =        "1984"
> , pages =       "125--129"
> , keywords =    "discrete geometry, decomposition, range search"
> , oldlabel =    "geom-899"
> }
> 
> % 2377 moved to 1513.2
> @article{c-lbcpr-89
> , author =      "B. Chazelle"
> , title =       "Lower bounds on the complexity of polytope range searching"
> , journal =     "J. Amer. Math. Soc."
> , volume =      "2"
> , year =        "1989"
> , pages =       "637--666"
> , keywords =    "simplex range searching, integral geometry, lower bounds"
> , oldlabel =    "geom-1513.2"
> }
> 
> @article{ce-lsdst-87
> , author =      "B. Chazelle and H. Edelsbrunner"
> , title =       "Linear space data structures for two types of range search"
> , journal =     "Discrete Comput. Geom."
> , volume =      "2"
> , year =        "1987"
> , pages =       "113--126"
> , keywords =    "data structuring, reporting, domination, range search, point location, directed acyclic graphs, two-dimensional, three-dimensional"
> , oldlabel =    "geom-756.2"
> }
> 
> @article{ce-oscpr-85
> , author =      "B. Chazelle and H. Edelsbrunner"
> , title =       "Optimal solutions for a class of point retrieval problems"
> , journal =     "J. Symbolic Comput."
> , volume =      "1"
> , year =        "1985"
> , pages =       "47--56"
> , keywords =    "data structuring, reporting, range search, directed acyclic graphs, translates"
> , oldlabel =    "geom-681"
> }
> 
> @inproceedings{cf-dvrsu-88
> , author =      "B. Chazelle and J. Friedman"
> , title =       "A deterministic view of random sampling and its use in geometry"
> , booktitle =   "Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci."
> , year =        "1988"
> , pages =       "539--549"
> , keywords =    "point location, range search, $d$-dimensional"
> , comments =    "derandomizes with polynomial overhead"
> , oldlabel =    "geom-2030.1"
> }
> 
> @article{cf-dvrsu-90
> , author =      "B. Chazelle and J. Friedman"
> , title =       "A deterministic view of random sampling and its use in geometry"
> , journal =     "Combinatorica"
> , volume =      "10"
> , number =      "3"
> , year =        "1990"
> , pages =       "229--249"
> , keywords =    "point location, range search, $d$-dimensional"
> , comments =    "derandomizes with polynomial overhead"
> , oldlabel =    "geom-2030.2"
> }
> 
> @article{c-narsc-87
> , author =      "K. L. Clarkson"
> , title =       "New applications of random sampling in computational geometry"
> , journal =     "Discrete Comput. Geom."
> , volume =      "2"
> , year =        "1987"
> , pages =       "195--222"
> , keywords =    "combinatorial geometry, data structuring, reporting, searching, separation, range search, point location, probabilistic analysis, triangulations, $d$-dimensional"
> , oldlabel =    "geom-688.2"
> }
> 
> @inproceedings{de-hstai-84
> , author =      "D. P. Dobkin and H. Edelsbrunner"
> , title =       "Ham-sandwich theorems applied to intersection problems"
> , booktitle =   "Proc. 10th Internat. Workshop Graph-Theoret. Concepts Comput. Sci. (WG 84)"
> , year =        "1984"
> , pages =       "88--99"
> , keywords =    "data structuring, discrete geometry, combinatorial geometry, partition, range search, trees, two-dimensional, three-dimensional"
> , oldlabel =    "geom-749"
> }
> 
> @article{de-ssio-87
> , author =      "D. P. Dobkin and H. Edelsbrunner"
> , title =       "Space searching for intersecting objects"
> , journal =     "J. Algorithms"
> , volume =      "8"
> , year =        "1987"
> , pages =       "348--361"
> , keywords =    "data structuring, discrete geometry, searching, intersection, partition, range search, geometric transformations, trees, two-dimensional, three-dimensional"
> , oldlabel =    "geom-694.2"
> }
> 
> @article{e-ndrs-81
> , author =      "H. Edelsbrunner"
> , title =       "A note on dynamic range searching"
> , journal =     "Bull. EATCS"
> , volume =      "15"
> , year =        "1981"
> , pages =       "34--40"
> , keywords =    "data structuring, searching, reporting, range search, range trees, priority search trees, points, hyperrectangles, $d$-dimensional"
> , oldlabel =    "geom-1620"
> }
> 
> @techreport{e-ddsoi-80
> , author =      "H. Edelsbrunner"
> , title =       "Dynamic data structures for orthogonal intersection queries"
> , type =        "Report"
> , number =      "F59"
> , institution = "Inst. Informationsverarb., Tech. Univ. Graz"
> , address =     "Graz, Austria"
> , year =        "1980"
> , keywords =    "data structuring, searching, intersection, dynamizing data structures, range trees, segment trees, interval trees, hyperrectangles, $d$-dimensional"
> , oldlabel =    "geom-183"
> }
> 
> @article{e-gatcg-87
> , author =      "H. Edelsbrunner"
> , title =       "Geometrics and algorithmics:  a tutorial in computational geometry"
> , journal =     "Bull. EATCS"
> , volume =      "32"
> , year =        "1987"
> , pages =       "118--142"
> , keywords =    "convex hull, range search, tutorial"
> , oldlabel =    "geom-1578"
> }
> 
> @techreport{eh-dsptt-84
> , author =      "H. Edelsbrunner and F. Huber"
> , title =       "Dissecting sets of points in two and three dimensions"
> , type =        "Report"
> , number =      "F138"
> , institution = "Inst. Informationsverarb., Tech. Univ. Graz"
> , address =     "Graz, Austria"
> , year =        "1984"
> , keywords =    "data structuring, discrete geometry, range search, trees, partition, cell complexes, two-dimensional, three-dimensional"
> , oldlabel =    "geom-701"
> }
> 
> @article{ekm-pis-82
> , author =      "H. Edelsbrunner and D. G. Kirkpatrick and H. A. Maurer"
> , title =       "Polygonal intersection searching"
> , journal =     "Inform. Process. Lett."
> , volume =      "14"
> , year =        "1982"
> , pages =       "74--79"
> , keywords =    "data structuring, reporting, intersection, range search, geometric transformations, points, line segments, polygons"
> , oldlabel =    "geom-1622"
> }
> 
> @article{em-ioo-81
> , author =      "H. Edelsbrunner and H. A. Maurer"
> , title =       "On the intersection of orthogonal objects"
> , journal =     "Inform. Process. Lett."
> , volume =      "13"
> , year =        "1981"
> , pages =       "177--181"
> , keywords =    "data structuring, searching, intersection, range trees, segment trees, interval trees, hyperrectangles, $d$-dimensional"
> , oldlabel =    "geom-1623"
> }
> 
> @article{eo-bdsds-85
> , author =      "H. Edelsbrunner and M. H. Overmars"
> , title =       "Batched dynamic solutions to decomposable searching problems"
> , journal =     "J. Algorithms"
> , volume =      "6"
> , year =        "1985"
> , pages =       "515--542"
> , keywords =    "design of algorithms, construction, reporting, divide-and-conquer, range trees, segment trees, $d$-dimensional"
> , oldlabel =    "geom-704"
> }
> 
> @article{eo-esrp-82
> , author =      "H. Edelsbrunner and M. H. Overmars"
> , title =       "On the equivalence of some rectangle problems"
> , journal =     "Inform. Process. Lett."
> , volume =      "14"
> , year =        "1982"
> , pages =       "124--127"
> , keywords =    "reporting, counting, range search, geometric transformations, lower bounds, intervals, one-dimensional, two-dimensional"
> , oldlabel =    "geom-1650"
> }
> 
> @article{eo-zrrd-87
> , author =      "H. Edelsbrunner and M. H. Overmars"
> , title =       "Zooming by repeated range detection"
> , journal =     "Inform. Process. Lett."
> , volume =      "24"
> , year =        "1987"
> , pages =       "413--417"
> , keywords =    "data structuring, computer graphics, reporting, range search, repeated search, trees, line segments, rectangles, two-dimensional"
> , oldlabel =    "geom-752"
> }
> 
> @article{eos-smcga-84
> , author =      "H. Edelsbrunner and M. H. Overmars and R. Seidel"
> , title =       "Some methods of computational geometry applied to computer graphics"
> , journal =     "Comput. Vision Graph. Image Process."
> , volume =      "28"
> , year =        "1984"
> , pages =       "92--108"
> , keywords =    "data structuring, computer graphics, construction, searching, point location, range search, trees, subdivisions, two-dimensional"
> , oldlabel =    "geom-745"
> }
> 
> @article{ew-cbtda-86
> , author =      "H. Edelsbrunner and E. Welzl"
> , title =       "Constructing belts in two-dimensional arrangements with applications"
> , journal =     "SIAM J. Comput."
> , volume =      "15"
> , year =        "1986"
> , pages =       "271--284"
> , keywords =    "design of algorithms, combinatorial geometry, plane-sweep, repeated search, arrangements, two-dimensional, counting, approximation, range search, arrangements"
> , oldlabel =    "geom-707"
> }
> 
> @article{ew-hrsls-86
> , author =      "H. Edelsbrunner and E. Welzl"
> , title =       "Halfplanar range search in linear space and {$O(n^{0.695})$} query time"
> , journal =     "Inform. Process. Lett."
> , volume =      "23"
> , year =        "1986"
> , pages =       "289--293"
> , keywords =    "data structuring, discrete geometry, searching, partition, range search, trees, subdivisions, two-dimensional, reporting, counting"
> , oldlabel =    "geom-708"
> }
> 
> @techreport{g-fdlsi-84
> , author =      "R. H. G{\"u}ting"
> , title =       "Fast dynamic line segment intersection searching"
> , type =        "Report"
> , number =      "87"
> , institution = "Forschungsberichte Fachber. Inform., Univ. Dortmund"
> , address =     "Dortmund, West Germany"
> , year =        "1984"
> , keywords =    "intersection searching, line segment, segment tree, range tree, halfobject technique"
> , oldlabel =    "geom-1073"
> }
> 
> @article{km-tcp-90
> , author =      "S. Khuller and J. S. B. Mitchell"
> , title =       "On a triangle counting problem"
> , journal =     "Inform. Process. Lett."
> , volume =      "33"
> , number =      "6"
> , year =        "1990"
> , pages =       "319--321"
> , keywords =    "range query, counting"
> , oldlabel =    "geom-2412"
> }
> 
> @article{know-dfwp-89
> , author =      "R. Klein and O. Nurmi and T. Ottmann and D. Wood"
> , title =       "A dynamic fixed windowing problem"
> , journal =     "Algorithmica"
> , volume =      "4"
> , year =        "1989"
> , pages =       "535--550"
> , keywords =    "points, range searching, polygons, two-dimensional, dynamizing data structures, priority search trees"
> , oldlabel =    "geom-808.3"
> }
> 
> @inproceedings{m-ept-91
> , author =      "J. Matou{\v s}ek"
> , title =       "Efficient partition trees"
> , booktitle =   "Proc. 7th Annu. ACM Sympos. Comput. Geom."
> , year =        "1991"
> , pages =       "1--9"
> , keywords =    "range search, simplex, partition trees"
> , oldlabel =    "geom-2568"
> }
> 
> @techreport{m-hsrr-90
> , author =      "J. Matou{\v s}ek"
> , title =       "Half-space range reporting"
> , series =      "KAM Series"
> , type =        "Report"
> , number =      "90-188"
> , institution = "Charles Univ."
> , address =     "Prague, Czechoslovakia"
> , year =        "1990"
> , keywords =    "range search, half spaces, polyhedra"
> , oldlabel =    "geom-2483"
> }
> 
> @inproceedings{m-oasrp-89
> , author =      "J. S. B. Mitchell"
> , title =       "An optimal algorithm for shortest rectilinear paths among obstacles"
> , booktitle =   "Proc. 1st Canad. Conf. Comput. Geom."
> , year =        "1989"
> , pages =       "22"
> , keywords =    "shortest paths, two-dimensional, distance, $L_{1}$ metric, continuous Dijkstra, plane-sweep, range search"
> , oldlabel =    "geom-2653"
> }
> 
> @article{m-lsppo-??
> , author =      "J. S. B. Mitchell"
> , title =       "{$L_{1}$} shortest paths among polygonal obstacles in the plane"
> , journal =     "Algorithmica"
> , volume =      "??"
> , year =        "19??"
> , pages =       "??--??"
> , keywords =    "shortest paths, distance, $L_{1}$ metric, continuous Dijkstra, plane-sweep, range search"
> , comments =    "to appear 1991?"
> , oldlabel =    "geom-1552.2"
> }
> 
> @inproceedings{m-srpo-87
> , author =      "J. S. B. Mitchell"
> , title =       "Shortest rectilinear paths among obstacles"
> , booktitle =   "Proc. 1st Internat. Conf. Indust. Applied Math."
> , address =     "Paris, France"
> , year =        "1987"
> , pages =       "39--84"
> , keywords =    "shortest paths, distance, $L_{1}$ metric, continuous Dijkstra, plane-sweep, range search"
> , oldlabel =    "geom-1552.1"
> }
> 
> @article{o-cg-88
> , author =      "J. O'Rourke"
> , title =       "Computational geometry"
> , journal =     "Annu. Rev. Comput. Sci."
> , volume =      "3"
> , year =        "1988"
> , pages =       "389--411"
> , keywords =    "survey paper, convex hull, Voronoi diagrams, Delaunay triangulations, arrangements, polygons, triangulation, range search, point location, motion planning, Davenport-Schinzel sequences, parallel computation"
> , oldlabel =    "geom-2122"
> }
> 
> @incollection{o-gdscg-88
> , author =      "M. H. Overmars"
> , title =       "Geometric data structures for computer graphics:  an overview"
> , editor =      "R. A. Earnshaw"
> , booktitle =   "Theoretical Foundations of Computer Graphics and CAD"
> , series =      "NATO ASI"
> , volume =      "F40"
> , publisher =   "Springer-Verlag"
> , year =        "1988"
> , pages =       "21--49"
> , keywords =    "survey paper, quad trees, range trees, segment trees, dynamizing data structures"
> , oldlabel =    "geom-2117.2"
> }
> 
> @article{ow-sms2d-85
> , author =      "M. H. Overmars and E. Welzl"
> , title =       "A simple method for solving {$2$}-dimensional static range searching"
> , journal =     "Bull. EATCS"
> , volume =      "25"
> , year =        "1985"
> , pages =       "31--33"
> , keywords =    "range search"
> , oldlabel =    "geom-1521"
> }
> 
> @techreport{s-cgru-89
> , author =      "J. Spiegels"
> , title =       "Computational geometry in a restricted universe"
> , type =        "Manuscript"
> , institution = "Dept. Comput. Sci., Univ. Utrecht"
> , year =        "1989"
> , keywords =    "survey paper, two-dimensional, domination, convex hull, rectangles, subdivisions, range search"
> , oldlabel =    "geom-2106"
> }
--
Ted Stockwell             There's a bit of magic in everything, 
ted@cs.umn.edu            And then some loss to even things out.   -- Lou Reed