home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / theory / 1802 < prev    next >
Encoding:
Internet Message Format  |  1992-08-22  |  20.5 KB
  1. Path: sparky!uunet!gatech!rutgers!news.cs.indiana.edu!umn.edu!cs.umn.edu!ted
  2. From: ted@cs.umn.edu (Ted Stockwell)
  3. Newsgroups: comp.theory
  4. Subject: SUMMARY: multidimensional range searching
  5. Message-ID: <TED.92Aug22095709@micro.cs.umn.edu>
  6. Date: 22 Aug 92 15:57:09 GMT
  7. Sender: news@news2.cis.umn.edu (Usenet News Administration)
  8. Organization: Midwest Software Journeymen
  9. Lines: 536
  10. Nntp-Posting-Host: micro.cs.umn.edu
  11.  
  12.  
  13. Below are the (slightly edited) responses I received to my request for
  14. information on multidimensional range searching.  Thanks to everyone
  15. who replied!
  16.  
  17. > From: dev@cs.brown.edu (Darren Erik Vengroff)
  18. > Organization: Brown University Department of Computer Science
  19. > 
  20. > Samet has written a pair of books that cover the area quite well.
  21. > They are
  22. > 
  23. > %A Hanan Samet
  24. > %T The Design and Analysis of Spatial Data Structures
  25. > %I Addison-Wesley
  26. > %D 1989
  27. > 
  28. > %A Hanan Samet
  29. > %T Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS
  30. > %I Addison-Wesley
  31. > %D 1989
  32. > 
  33. > If what you are looking for is not in one of these books it is sure
  34. > to be in one of the several hundred entries in the bibliography.
  35. > 
  36. > -Darren
  37. > 
  38. > 
  39. > From: Peter Su <psu@cs.duke.edu>
  40. > Status: OR
  41. > 
  42. > Look in Preperata and Shamos: _Computational Geometry_ and also a book
  43. > by Samet _Spatial data structures_ for a good overview.
  44. > 
  45. > Oh, also, Kurt Melhorn has a 3 vol. set of algorithms books, and the
  46. > third volume covers multi-dimensional searching.
  47. > 
  48. > There is a lot of heavy theory in Melhorn and P&S...Samet is more
  49. > application oriented- spatial databases and what not.
  50. > 
  51. > 
  52. > From: salzberg@corwin.ccs.northeastern.edu (betty j salzberg)
  53. > 
  54. > an article Dave Lomet wrote will appear in the next sigmod record. IT
  55. > is about multiattribute range searching. It is short and has good
  56. > insights.
  57. > 
  58. > 
  59. > From: rbaeza@dcc.uchile.cl (Ricardo Baeza)
  60. > For a complete set of references on the topic, check
  61. > "Handbook of Algorithms and Data Structures", Addison-Wesley, 2nd edition,
  62. > 1991 by Gonnet and myself.
  63. > 
  64. > 
  65. > From: enni@imada.ou.dk (Steffen Zacho Enni)
  66. > 
  67. > I have been looking for the same things. And the best I have found
  68. > is Bentleys article in CACM 1975 (page 517-29, I think).
  69. > 
  70. > In this article he introduces the k-d tree and some algorithms
  71. > There is an algorithm to range searching.
  72. > 
  73. > In another article by Bentley, Friedmann and Finkel ( "An Algorithm
  74. > for Finding Best Matches in Logarithmic Expected Time" by
  75. > J.H.Friedman, J.L.Bentley and R.A.Finkel. And it appeared in ACM
  76. > Transactions on Mathematical Software, Vol. 3, No. 3, September 1977,
  77. > Pages 209-226.) they present a slight variation of the k-d tree with
  78. > an algorithm to finding nearest neighbors with every distance function
  79. > you may wish. It runs in O(lg n) with O(nlgn) building time.
  80. > 
  81. > Shamos in his Introduction to computational Geometry also 
  82. > contain some information about this subject, but it is
  83. > presented in a more general way.
  84. > 
  85. > 
  86. > From: aronov@ziggy.poly.edu (Boris Aronov)
  87. > 
  88. > This is all I could find in the computational geometry data base under
  89. > range queries. Most of them ARE multidimensional (in the sense of not
  90. > being 1-dimensional), but the types of queries varies very widely.
  91. > 
  92. > Hope this helps...
  93. > 
  94. >         40 matches found.
  95. > 
  96. > @inproceedings{am-rsps-92
  97. > , author =      "P. K. Agarwal and J. Matou{\v s}ek"
  98. > , title =       "Ray shooting and parametric search"
  99. > , booktitle =   "Proc. 24th Annu. ACM Sympos. Theory Comput."
  100. > , year =        "1992"
  101. > , pages =       "??-??"
  102. > , keywords =    "ray tracing, range search, intersection, partition trees"
  103. > , comments =    "To appear"
  104. > , oldlabel =    "geom-2481"
  105. > }
  106. > 
  107. > @inproceedings{as-anps-91
  108. > , author =      "P. K. Agarwal and M. Sharir"
  109. > , title =       "Applications of a new partitioning scheme"
  110. > , booktitle =   "Proc. 2nd Workshop Algorithms Data Struct."
  111. > , series =      "Lecture Notes in Computer Science"
  112. > , volume =      "519"
  113. > , publisher =   "Springer-Verlag"
  114. > , year =        "1991"
  115. > , pages =       "379--391"
  116. > , keywords =    "random sampling, range searching, ray tracing, hidden line/surface elimination"
  117. > , oldlabel =    "geom-2625"
  118. > }
  119. > 
  120. > @inproceedings{avo-iqco-91
  121. > , author =      "P. K. Agarwal and M. van~Kreveld and M. Overmars"
  122. > , title =       "Intersection queries for curved objects"
  123. > , booktitle =   "Proc. 7th Annu. ACM Sympos. Comput. Geom."
  124. > , year =        "1991"
  125. > , pages =       "41--50"
  126. > , keywords =    "range searching, partition trees, intersection"
  127. > , oldlabel =    "geom-2572"
  128. > }
  129. > 
  130. > @incollection{aeiim-pubtc-85
  131. > , author =      "Ta. Asano and M. Edahiro and H. Imai and M. Iri and K. Murota"
  132. > , title =       "Practical use of bucketing techniques in computational geometry"
  133. > , editor =      "G. T. Toussaint"
  134. > , booktitle =   "Computational Geometry"
  135. > , publisher =   "North-Holland"
  136. > , address =     "Amsterdam, Netherlands"
  137. > , year =        "1985"
  138. > , pages =       "153--195"
  139. > , keywords =    "survey paper, implementing algorithms, optimization, bucketing, matchings, Voronoi diagrams, range search, point location, quad trees"
  140. > , oldlabel =    "geom-1024"
  141. > }
  142. > 
  143. > @article{acg-cdctd-89
  144. > , author =      "M. J. Atallah and R. Cole and M. T. Goodrich"
  145. > , title =       "Cascading divide-and-conquer:  {A} technique for designing parallel algorithms"
  146. > , journal =     "SIAM J. Comput."
  147. > , volume =      "18"
  148. > , year =        "1989"
  149. > , pages =       "499--532"
  150. > , keywords =    "parallel computation, decomposition, range search, point location, visibility, domination, points, lines, divide-and-conquer, two-dimensional"
  151. > , oldlabel =    "geom-901.2"
  152. > }
  153. > 
  154. > @inproceedings{ag-epsp-86
  155. > , author =      "M. J. Atallah and M. T. Goodrich"
  156. > , title =       "Efficient plane sweeping in parallel"
  157. > , booktitle =   "Proc. 2nd Annu. ACM Sympos. Comput. Geom."
  158. > , year =        "1986"
  159. > , pages =       "216--225"
  160. > , keywords =    "parallel computation, decomposition, range search, point location, triangulation, visibility, domination, points, lines, two-dimensional"
  161. > , oldlabel =    "geom-820"
  162. > }
  163. > 
  164. > @inproceedings{as-ddsrs-81
  165. > , author =      "Z. Aviad and E. Shamir"
  166. > , title =       "A direct dynamic solution to range search and related problems for product regions"
  167. > , booktitle =   "Proc. 22nd Annu. IEEE Sympos. Found. Comput. Sci."
  168. > , year =        "1981"
  169. > , pages =       "123--126"
  170. > , keywords =    "orthogonal range queries, integer coordinates, multidimensional search"
  171. > , oldlabel =    "geom-21"
  172. > }
  173. > 
  174. > @article{a-npps-84
  175. > , author =      "D. Avis"
  176. > , title =       "Non-partitionable point sets"
  177. > , journal =     "Inform. Process. Lett."
  178. > , volume =      "19"
  179. > , year =        "1984"
  180. > , pages =       "125--129"
  181. > , keywords =    "discrete geometry, decomposition, range search"
  182. > , oldlabel =    "geom-899"
  183. > }
  184. > 
  185. > % 2377 moved to 1513.2
  186. > @article{c-lbcpr-89
  187. > , author =      "B. Chazelle"
  188. > , title =       "Lower bounds on the complexity of polytope range searching"
  189. > , journal =     "J. Amer. Math. Soc."
  190. > , volume =      "2"
  191. > , year =        "1989"
  192. > , pages =       "637--666"
  193. > , keywords =    "simplex range searching, integral geometry, lower bounds"
  194. > , oldlabel =    "geom-1513.2"
  195. > }
  196. > 
  197. > @article{ce-lsdst-87
  198. > , author =      "B. Chazelle and H. Edelsbrunner"
  199. > , title =       "Linear space data structures for two types of range search"
  200. > , journal =     "Discrete Comput. Geom."
  201. > , volume =      "2"
  202. > , year =        "1987"
  203. > , pages =       "113--126"
  204. > , keywords =    "data structuring, reporting, domination, range search, point location, directed acyclic graphs, two-dimensional, three-dimensional"
  205. > , oldlabel =    "geom-756.2"
  206. > }
  207. > 
  208. > @article{ce-oscpr-85
  209. > , author =      "B. Chazelle and H. Edelsbrunner"
  210. > , title =       "Optimal solutions for a class of point retrieval problems"
  211. > , journal =     "J. Symbolic Comput."
  212. > , volume =      "1"
  213. > , year =        "1985"
  214. > , pages =       "47--56"
  215. > , keywords =    "data structuring, reporting, range search, directed acyclic graphs, translates"
  216. > , oldlabel =    "geom-681"
  217. > }
  218. > 
  219. > @inproceedings{cf-dvrsu-88
  220. > , author =      "B. Chazelle and J. Friedman"
  221. > , title =       "A deterministic view of random sampling and its use in geometry"
  222. > , booktitle =   "Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci."
  223. > , year =        "1988"
  224. > , pages =       "539--549"
  225. > , keywords =    "point location, range search, $d$-dimensional"
  226. > , comments =    "derandomizes with polynomial overhead"
  227. > , oldlabel =    "geom-2030.1"
  228. > }
  229. > 
  230. > @article{cf-dvrsu-90
  231. > , author =      "B. Chazelle and J. Friedman"
  232. > , title =       "A deterministic view of random sampling and its use in geometry"
  233. > , journal =     "Combinatorica"
  234. > , volume =      "10"
  235. > , number =      "3"
  236. > , year =        "1990"
  237. > , pages =       "229--249"
  238. > , keywords =    "point location, range search, $d$-dimensional"
  239. > , comments =    "derandomizes with polynomial overhead"
  240. > , oldlabel =    "geom-2030.2"
  241. > }
  242. > 
  243. > @article{c-narsc-87
  244. > , author =      "K. L. Clarkson"
  245. > , title =       "New applications of random sampling in computational geometry"
  246. > , journal =     "Discrete Comput. Geom."
  247. > , volume =      "2"
  248. > , year =        "1987"
  249. > , pages =       "195--222"
  250. > , keywords =    "combinatorial geometry, data structuring, reporting, searching, separation, range search, point location, probabilistic analysis, triangulations, $d$-dimensional"
  251. > , oldlabel =    "geom-688.2"
  252. > }
  253. > 
  254. > @inproceedings{de-hstai-84
  255. > , author =      "D. P. Dobkin and H. Edelsbrunner"
  256. > , title =       "Ham-sandwich theorems applied to intersection problems"
  257. > , booktitle =   "Proc. 10th Internat. Workshop Graph-Theoret. Concepts Comput. Sci. (WG 84)"
  258. > , year =        "1984"
  259. > , pages =       "88--99"
  260. > , keywords =    "data structuring, discrete geometry, combinatorial geometry, partition, range search, trees, two-dimensional, three-dimensional"
  261. > , oldlabel =    "geom-749"
  262. > }
  263. > 
  264. > @article{de-ssio-87
  265. > , author =      "D. P. Dobkin and H. Edelsbrunner"
  266. > , title =       "Space searching for intersecting objects"
  267. > , journal =     "J. Algorithms"
  268. > , volume =      "8"
  269. > , year =        "1987"
  270. > , pages =       "348--361"
  271. > , keywords =    "data structuring, discrete geometry, searching, intersection, partition, range search, geometric transformations, trees, two-dimensional, three-dimensional"
  272. > , oldlabel =    "geom-694.2"
  273. > }
  274. > 
  275. > @article{e-ndrs-81
  276. > , author =      "H. Edelsbrunner"
  277. > , title =       "A note on dynamic range searching"
  278. > , journal =     "Bull. EATCS"
  279. > , volume =      "15"
  280. > , year =        "1981"
  281. > , pages =       "34--40"
  282. > , keywords =    "data structuring, searching, reporting, range search, range trees, priority search trees, points, hyperrectangles, $d$-dimensional"
  283. > , oldlabel =    "geom-1620"
  284. > }
  285. > 
  286. > @techreport{e-ddsoi-80
  287. > , author =      "H. Edelsbrunner"
  288. > , title =       "Dynamic data structures for orthogonal intersection queries"
  289. > , type =        "Report"
  290. > , number =      "F59"
  291. > , institution = "Inst. Informationsverarb., Tech. Univ. Graz"
  292. > , address =     "Graz, Austria"
  293. > , year =        "1980"
  294. > , keywords =    "data structuring, searching, intersection, dynamizing data structures, range trees, segment trees, interval trees, hyperrectangles, $d$-dimensional"
  295. > , oldlabel =    "geom-183"
  296. > }
  297. > 
  298. > @article{e-gatcg-87
  299. > , author =      "H. Edelsbrunner"
  300. > , title =       "Geometrics and algorithmics:  a tutorial in computational geometry"
  301. > , journal =     "Bull. EATCS"
  302. > , volume =      "32"
  303. > , year =        "1987"
  304. > , pages =       "118--142"
  305. > , keywords =    "convex hull, range search, tutorial"
  306. > , oldlabel =    "geom-1578"
  307. > }
  308. > 
  309. > @techreport{eh-dsptt-84
  310. > , author =      "H. Edelsbrunner and F. Huber"
  311. > , title =       "Dissecting sets of points in two and three dimensions"
  312. > , type =        "Report"
  313. > , number =      "F138"
  314. > , institution = "Inst. Informationsverarb., Tech. Univ. Graz"
  315. > , address =     "Graz, Austria"
  316. > , year =        "1984"
  317. > , keywords =    "data structuring, discrete geometry, range search, trees, partition, cell complexes, two-dimensional, three-dimensional"
  318. > , oldlabel =    "geom-701"
  319. > }
  320. > 
  321. > @article{ekm-pis-82
  322. > , author =      "H. Edelsbrunner and D. G. Kirkpatrick and H. A. Maurer"
  323. > , title =       "Polygonal intersection searching"
  324. > , journal =     "Inform. Process. Lett."
  325. > , volume =      "14"
  326. > , year =        "1982"
  327. > , pages =       "74--79"
  328. > , keywords =    "data structuring, reporting, intersection, range search, geometric transformations, points, line segments, polygons"
  329. > , oldlabel =    "geom-1622"
  330. > }
  331. > 
  332. > @article{em-ioo-81
  333. > , author =      "H. Edelsbrunner and H. A. Maurer"
  334. > , title =       "On the intersection of orthogonal objects"
  335. > , journal =     "Inform. Process. Lett."
  336. > , volume =      "13"
  337. > , year =        "1981"
  338. > , pages =       "177--181"
  339. > , keywords =    "data structuring, searching, intersection, range trees, segment trees, interval trees, hyperrectangles, $d$-dimensional"
  340. > , oldlabel =    "geom-1623"
  341. > }
  342. > 
  343. > @article{eo-bdsds-85
  344. > , author =      "H. Edelsbrunner and M. H. Overmars"
  345. > , title =       "Batched dynamic solutions to decomposable searching problems"
  346. > , journal =     "J. Algorithms"
  347. > , volume =      "6"
  348. > , year =        "1985"
  349. > , pages =       "515--542"
  350. > , keywords =    "design of algorithms, construction, reporting, divide-and-conquer, range trees, segment trees, $d$-dimensional"
  351. > , oldlabel =    "geom-704"
  352. > }
  353. > 
  354. > @article{eo-esrp-82
  355. > , author =      "H. Edelsbrunner and M. H. Overmars"
  356. > , title =       "On the equivalence of some rectangle problems"
  357. > , journal =     "Inform. Process. Lett."
  358. > , volume =      "14"
  359. > , year =        "1982"
  360. > , pages =       "124--127"
  361. > , keywords =    "reporting, counting, range search, geometric transformations, lower bounds, intervals, one-dimensional, two-dimensional"
  362. > , oldlabel =    "geom-1650"
  363. > }
  364. > 
  365. > @article{eo-zrrd-87
  366. > , author =      "H. Edelsbrunner and M. H. Overmars"
  367. > , title =       "Zooming by repeated range detection"
  368. > , journal =     "Inform. Process. Lett."
  369. > , volume =      "24"
  370. > , year =        "1987"
  371. > , pages =       "413--417"
  372. > , keywords =    "data structuring, computer graphics, reporting, range search, repeated search, trees, line segments, rectangles, two-dimensional"
  373. > , oldlabel =    "geom-752"
  374. > }
  375. > 
  376. > @article{eos-smcga-84
  377. > , author =      "H. Edelsbrunner and M. H. Overmars and R. Seidel"
  378. > , title =       "Some methods of computational geometry applied to computer graphics"
  379. > , journal =     "Comput. Vision Graph. Image Process."
  380. > , volume =      "28"
  381. > , year =        "1984"
  382. > , pages =       "92--108"
  383. > , keywords =    "data structuring, computer graphics, construction, searching, point location, range search, trees, subdivisions, two-dimensional"
  384. > , oldlabel =    "geom-745"
  385. > }
  386. > 
  387. > @article{ew-cbtda-86
  388. > , author =      "H. Edelsbrunner and E. Welzl"
  389. > , title =       "Constructing belts in two-dimensional arrangements with applications"
  390. > , journal =     "SIAM J. Comput."
  391. > , volume =      "15"
  392. > , year =        "1986"
  393. > , pages =       "271--284"
  394. > , keywords =    "design of algorithms, combinatorial geometry, plane-sweep, repeated search, arrangements, two-dimensional, counting, approximation, range search, arrangements"
  395. > , oldlabel =    "geom-707"
  396. > }
  397. > 
  398. > @article{ew-hrsls-86
  399. > , author =      "H. Edelsbrunner and E. Welzl"
  400. > , title =       "Halfplanar range search in linear space and {$O(n^{0.695})$} query time"
  401. > , journal =     "Inform. Process. Lett."
  402. > , volume =      "23"
  403. > , year =        "1986"
  404. > , pages =       "289--293"
  405. > , keywords =    "data structuring, discrete geometry, searching, partition, range search, trees, subdivisions, two-dimensional, reporting, counting"
  406. > , oldlabel =    "geom-708"
  407. > }
  408. > 
  409. > @techreport{g-fdlsi-84
  410. > , author =      "R. H. G{\"u}ting"
  411. > , title =       "Fast dynamic line segment intersection searching"
  412. > , type =        "Report"
  413. > , number =      "87"
  414. > , institution = "Forschungsberichte Fachber. Inform., Univ. Dortmund"
  415. > , address =     "Dortmund, West Germany"
  416. > , year =        "1984"
  417. > , keywords =    "intersection searching, line segment, segment tree, range tree, halfobject technique"
  418. > , oldlabel =    "geom-1073"
  419. > }
  420. > 
  421. > @article{km-tcp-90
  422. > , author =      "S. Khuller and J. S. B. Mitchell"
  423. > , title =       "On a triangle counting problem"
  424. > , journal =     "Inform. Process. Lett."
  425. > , volume =      "33"
  426. > , number =      "6"
  427. > , year =        "1990"
  428. > , pages =       "319--321"
  429. > , keywords =    "range query, counting"
  430. > , oldlabel =    "geom-2412"
  431. > }
  432. > 
  433. > @article{know-dfwp-89
  434. > , author =      "R. Klein and O. Nurmi and T. Ottmann and D. Wood"
  435. > , title =       "A dynamic fixed windowing problem"
  436. > , journal =     "Algorithmica"
  437. > , volume =      "4"
  438. > , year =        "1989"
  439. > , pages =       "535--550"
  440. > , keywords =    "points, range searching, polygons, two-dimensional, dynamizing data structures, priority search trees"
  441. > , oldlabel =    "geom-808.3"
  442. > }
  443. > 
  444. > @inproceedings{m-ept-91
  445. > , author =      "J. Matou{\v s}ek"
  446. > , title =       "Efficient partition trees"
  447. > , booktitle =   "Proc. 7th Annu. ACM Sympos. Comput. Geom."
  448. > , year =        "1991"
  449. > , pages =       "1--9"
  450. > , keywords =    "range search, simplex, partition trees"
  451. > , oldlabel =    "geom-2568"
  452. > }
  453. > 
  454. > @techreport{m-hsrr-90
  455. > , author =      "J. Matou{\v s}ek"
  456. > , title =       "Half-space range reporting"
  457. > , series =      "KAM Series"
  458. > , type =        "Report"
  459. > , number =      "90-188"
  460. > , institution = "Charles Univ."
  461. > , address =     "Prague, Czechoslovakia"
  462. > , year =        "1990"
  463. > , keywords =    "range search, half spaces, polyhedra"
  464. > , oldlabel =    "geom-2483"
  465. > }
  466. > 
  467. > @inproceedings{m-oasrp-89
  468. > , author =      "J. S. B. Mitchell"
  469. > , title =       "An optimal algorithm for shortest rectilinear paths among obstacles"
  470. > , booktitle =   "Proc. 1st Canad. Conf. Comput. Geom."
  471. > , year =        "1989"
  472. > , pages =       "22"
  473. > , keywords =    "shortest paths, two-dimensional, distance, $L_{1}$ metric, continuous Dijkstra, plane-sweep, range search"
  474. > , oldlabel =    "geom-2653"
  475. > }
  476. > 
  477. > @article{m-lsppo-??
  478. > , author =      "J. S. B. Mitchell"
  479. > , title =       "{$L_{1}$} shortest paths among polygonal obstacles in the plane"
  480. > , journal =     "Algorithmica"
  481. > , volume =      "??"
  482. > , year =        "19??"
  483. > , pages =       "??--??"
  484. > , keywords =    "shortest paths, distance, $L_{1}$ metric, continuous Dijkstra, plane-sweep, range search"
  485. > , comments =    "to appear 1991?"
  486. > , oldlabel =    "geom-1552.2"
  487. > }
  488. > 
  489. > @inproceedings{m-srpo-87
  490. > , author =      "J. S. B. Mitchell"
  491. > , title =       "Shortest rectilinear paths among obstacles"
  492. > , booktitle =   "Proc. 1st Internat. Conf. Indust. Applied Math."
  493. > , address =     "Paris, France"
  494. > , year =        "1987"
  495. > , pages =       "39--84"
  496. > , keywords =    "shortest paths, distance, $L_{1}$ metric, continuous Dijkstra, plane-sweep, range search"
  497. > , oldlabel =    "geom-1552.1"
  498. > }
  499. > 
  500. > @article{o-cg-88
  501. > , author =      "J. O'Rourke"
  502. > , title =       "Computational geometry"
  503. > , journal =     "Annu. Rev. Comput. Sci."
  504. > , volume =      "3"
  505. > , year =        "1988"
  506. > , pages =       "389--411"
  507. > , keywords =    "survey paper, convex hull, Voronoi diagrams, Delaunay triangulations, arrangements, polygons, triangulation, range search, point location, motion planning, Davenport-Schinzel sequences, parallel computation"
  508. > , oldlabel =    "geom-2122"
  509. > }
  510. > 
  511. > @incollection{o-gdscg-88
  512. > , author =      "M. H. Overmars"
  513. > , title =       "Geometric data structures for computer graphics:  an overview"
  514. > , editor =      "R. A. Earnshaw"
  515. > , booktitle =   "Theoretical Foundations of Computer Graphics and CAD"
  516. > , series =      "NATO ASI"
  517. > , volume =      "F40"
  518. > , publisher =   "Springer-Verlag"
  519. > , year =        "1988"
  520. > , pages =       "21--49"
  521. > , keywords =    "survey paper, quad trees, range trees, segment trees, dynamizing data structures"
  522. > , oldlabel =    "geom-2117.2"
  523. > }
  524. > 
  525. > @article{ow-sms2d-85
  526. > , author =      "M. H. Overmars and E. Welzl"
  527. > , title =       "A simple method for solving {$2$}-dimensional static range searching"
  528. > , journal =     "Bull. EATCS"
  529. > , volume =      "25"
  530. > , year =        "1985"
  531. > , pages =       "31--33"
  532. > , keywords =    "range search"
  533. > , oldlabel =    "geom-1521"
  534. > }
  535. > 
  536. > @techreport{s-cgru-89
  537. > , author =      "J. Spiegels"
  538. > , title =       "Computational geometry in a restricted universe"
  539. > , type =        "Manuscript"
  540. > , institution = "Dept. Comput. Sci., Univ. Utrecht"
  541. > , year =        "1989"
  542. > , keywords =    "survey paper, two-dimensional, domination, convex hull, rectangles, subdivisions, range search"
  543. > , oldlabel =    "geom-2106"
  544. > }
  545. --
  546. Ted Stockwell             There's a bit of magic in everything, 
  547. ted@cs.umn.edu            And then some loss to even things out.   -- Lou Reed
  548.