User:NikolasCo

From Wikipedia, the free encyclopedia

Wikipedia:Babel
en This user is a native speaker of English.
\sum This user is greater than the sum of his or her userboxes.
@ This user can be reached by email.
This user uses Jabber as nikolasco@livejournal.com.
This user's AOL Instant Messenger screenname is atrustheotaku.
Y! This user's Yahoo! Messenger screename is atrustheotaku.
This user uses MSN Messenger and his/her e-mail address is atrustheotaku@hotmail.com
This user contributes using Linux.
This user runs Mac OS X.
non This user is full of non sequiturs.
Fix my saxophone!
prog This user is a programmer.
Search user languages

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."