BSP tree, kd tree, convex, space partitioning

. BSP tree
http://en.wikipedia.org/wiki/BSP_tree
Binary space partitioning
recursive하게 space를 convex set으로 subdivide함.

. kd-tree
http://en.wikipedia.org/wiki/Kd-tree
BSP tree의 일종
plane을 perpendicular하게 분할
각 공간에 점이 1개 이상 들어가게 나눔.
사각형 안에 있는 모든 점을 찾을 때 이용

. convex
http://en.wikipedia.org/wiki/Convex_set
object내의 모든 straight line segment위의 점이 역시 object있음.

. convex set
두 convex 내의 point를 잇는 line segment내의 모든 point의 모임.

. space partitioning
http://en.wikipedia.org/wiki/Space_partitioning
공간은 disjoin subset으로 나눔.

. KDB-tree
kd-tree와 비슷하게 분할하지만 결과가 B-tree가 됨

. LSD-tree
Local split decision tree

. EXCELL
A point access method using a dynamic multidimensional array

. grid file
A point access method which splits space into a nonperiodic grid. Each spatial dimension is divided by a linear hash. Small sets of points are reffered to by one or more cells of the grid.

. buddy hash tree
http://www.dbs.informatik.uni-muenchen.de/Publikationen/Papers/Buddy_Tree_1990.pdf

. BANG file
http://www.nist.gov/dads/HTML/bangfile.html
A balanced and nested grid(BANG) file is a point access method which divides space into a nonperiodic grid. Each spatial dimension is divided by a linear hash. Cells may intersect, and points may be distributed between them.

. hB-tree
http://www.nist.gov/dads/HTML/hbtree.html
A point access method which uses k-d trees to organize the space, but partitions as excluded intervals, like the BANG file. Searching is like in a k-d-B-tree.