topical media & game development

talk show tell print

Multimedia data structures

Multimedia data structures

2d, 3d, space-time

slide: Multimedia data structures

Hierarchical decompositions -- tree

  • k-d tree
  • point quad tree
  • MX quad tree
  • R-trees
  • TV trees

slide: Hierarchical decomposition

k-d trees -- node structure (k = 2)

  nodetype = record
    info : infotype;
    xval : real;
    yval : real;
    llink : *nodetype;
    rlink : *nodetype;

slide: k-d trees -- node structure


  	    0             if N is the root
  level(N) =
  	    level(P) + 1  if N's parent is P


  level(N) even:  L is subtree at N.llink: L.xval < N.xval
  		R is subtree at N.rlink: R.xval >= N.xval
  level(N) odd:   L is subtree at N.llink: L.yval < N.yval
  		R is subtree at N.rlink: R.yval >= N.yval 

slide: Definition and constraints

Insertion -- node N

try T, level(T) is even
if T.xval = N.xval & T.yval = N.yval then T = N; else if N.xval < T.val then branch left else if N.xval >= T.val then branch right



slide: Insertion

Deletion -- node N

    1. search for node N
    2. if N is leaf, delete
        1. find candidate replacement node K in T1, i e {l,r}
        2. replace N's non-links fields by those of K
        3. delete K from Ti

slide: Deletion

Conditions -- K must satisfy

    1. level(N) even: 
  	all L in Tl, L.xval < K.xval
          all R in Tr, R.xval >= K.xval
    2. level(N) odd :
  	all L in Tl, L.yval < K.yval
          all R in Tr, R.yval >= K.yval

Heuristics - right subtree, Tr not empty

  • label(N) even, node with smallest xval in Tr
  • label(N) odd, node with smallest yval in Tr

left subtree

  • maximal xval or yval, must be unique

slide: Conditions -- replacement node

Range queries

  • a range query wrt. a 2-d tree T is a query that specifies a point (x_c,y_c) and distance r


  • set of all points $(x,y) s.t. $(x,y) within distance r from $(x_c,y_c)

slide: Range queries

Range and nodes

  • each node in a 2-d tree implicitly represents a region R_N.
  • in general, each node N has at most four associated constraints that jointly define the region represented by that node.


     XLB: x >= c1; XUB: x < c2; YLB: y >= c3; XUB: y < c4;

slide: Ranges and nodes

slide: Regions and bounds


  • 1. root: XLB = YLB = -inf; XUB = YUB = inf
  • 2. node N has node P as its parent and level(P) is even:

    N.xlb = P.xlb  if N = P.llink
    N.xlb = P.xval if N = P.rlink
    N.xub = P.xval if N = P.llink
    N.xub = P.xub  if N = P.rlink
    N.ylb = P.ylb; N.yub = P.yub
  • 3. node N has node P as its parent and level(P) is odd:

    N.ylb = P.ylb  if N = P.llink
    N.ylb = P.yval if N = P.rlink
    N.yub = P.yval if N = P.llink
    N.yub = P.yub  if N = P.rlink
    N.xlb = P.xlb; N.xub = P.xub

slide: Bounds -- conditions

(C) Æliens 04/09/2009

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.