From Wikipedia, the free encyclopedia
I am Nikolas Coukouma, sometimes referred to as Atrus online (note: Atrus is a different person). I'm currently an undergraduate Computer science major at the University of Maryland, College Park. My blog is probably the best source for information about me, although I do have a personal site.
Current to-do list:
- Add
- Point quadtree
- Point region quadtree, redirect PR quadtree to this
- MX quadtree
- Edge quadtree
- Polygonal map quadtree, redirect PM quadtree to this
- Range tree
- Expand
- kd-tree
- complete
- section on orthogonal search
- possibly deletion (ow)
- Add more info on
- complexity
- include sliding-midpoint
- B*-tree
- B plus tree
- Selection algorithm - add best known deterministic (3n) and randomized algorithms (1.5n)
- Reorganize
- Quadtree - add the above quadtrees to the list, pull PR out
Notes for myself:
Papers to find:
- D. E. Willard, Balanced forests of k-d* trees as a dynamic data structure, Aiken Computation Lab TR-23-78, Harvard University, Cambridge, 1978. (ancient tech report, no idea where to get a copy)
- V. K. Vaishnavi, Multidimensional height-balanced trees, IEEE Transactions on Computers 33, 4(April1984), 334-343. (available on microfilm, yay)
- D. T. Lee and B. J. Shacter, Two algorithms for contructing a Delaunay Triangulation, International Journal of Computer and Information Science 9, 3(June 1980), 219-242 (not available from UMAI ...)
- Linn, J. C. 1973 General Methods for Parallel-Searching.. Doctoral Thesis. UMI Order Number: AAI7330429. (Samet says it was published as Technical Report 81, Digital Systems Laboratory, Stanford University, CA, May 1973.)
Requested:
- D. T. Lee and C. K. Wong, Worst-case analysis for region and partial region searches in multidimensional binary search trees and quad treesm Acta Informatica 9, 1(1977), 23-29
- M. H. Overmars and J. van Leeuwen, Dynamic multi-dimensional data structures based on quad- and k-d trees, Acta Informatica 17, 3(1982), 267-285.
Pull of the shelf: TAOCP Vol 3, mentioned by Samet: "the k-d tree can be used to handle all three queries specified by Knuth. The Range query is described above. Simple queries are a by-product of the k-d tree insertion process Boolean queries are straightforward. Range queries can be facilitates by use of a bounds array B[i] of 2k elements stored at each node. It contains the range of values for all of the coordinates of the points stored in the ke-d tree rooted at the node."
