Collision Detection

• Minimum Volume 3d Enclosing Box with Arbitrary Orientation
  
  
  • Project (7.5 ETCS, can be extended): Implementation of a fast heuristic or approximation algorithm for the minimum volume box enclosing a set of points in 3d with arbitrary orientation. Applications: Collision detection. There is an O(n^3) exact algorithm, see J. O'Rourke, Finding minimal enclosing boxes, Int. J. of Parallel Programming 14 (1985) 183-189. This is too slow.
    
    Good starting point for approximation algorithms is probably G. Barequet and S. Har-Peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions J. of Algorithms 38 (2001) 91-109.
    
    In 2 dimensions, this problem can be solved in O(nlogn) time, see for example G.T. Toussaint, Solving geometric problems with the rotating calipers" Proc. of IEEE MELECON'83, Athens, Greece, 1983.