Hongjun Zhu <hongjunz@cs.ucsb.edu>
http://www.cs.ucsb.edu/~hongjunz

Octagons, octagon trees, and moving objects trajectories
  An important class of queries in moving object databases are queries over
  their trajectories.  In most cases, trajectories are modeled as chains of
  line segments.  Point search, line search, and polygon based region search
  are fundamental operations in evaluation of trajectory queries.  Similar
  to searches in traditional spatial databases, these searches can be
  performed in the following two steps: (1) a filter step that applies the
  searches to the minimum bounding rectangles (MBRs) of the trajectories,
  and (2) a refinement step that applies the queries on the trajectories
  reported by the filter step.  Unfortunately, MBRs are very coarse
  approximations for trajectories.  In this paper, we separate space and
  time when approximating trajectories and focus on approximating the space
  components of trajectories.  In particular, we propose a new type of
  approximations based on ``convex octagons''.  A minimum bounding (convex)
  octagon (MBO) of an object is an octagon with the smallest area where two
  pairs of two opposite sides must be parallel to each axis.  For linear
  trajectories, our algorithm generates an MBO by cutting off the four
  corners of the MBR.  We develope a new index
  structure, ``Octagon-trees'', for 2 dimensional objects and an extension,
  ``Octagon-trees with time'', for trajectories of 2 dimensional moving
  points.  Experiments show that Octagon-trees with time improve region
  searches significantly over trajectories generated by the GSTD algorithm
  and a network-based generator by Brinkhoff.  In particular, both 
  the I/O cost and the CPU cost are reduced by about 30%.
  In order to understand the impact of the octagon
  index technique, we also compared Octagon-trees with 2-d R*-trees.  The
  results show that Octagon-trees out-perform R*-trees for point,
  line, and window searches when the size of query windowes are small.