M’Sadoques defends MS dissertation on translational single-item containment

On April 4, 2011, Jason M’Sadoques successfully defended his MS dissertation, entitled “Regarding an Alternative Method for Translational Single-Item Containment.” This work, supported by adviser Dr. Karen Daniels, took an idea originally presented by Althaus et al. that obtained the feasible region for placing an object into a container without the use of unbounded point sets. The thesis supplied a formal proof and also presented the restrictions on its validity.

The use of unbounded point sets requires special handling in computational geometry. One method is to calculate or estimate a maximum volume of space in which all geometric manipulations will fit: a bounding box. Alternatively there is a technique called infimaximal frames. Neither option was suitable for use in this case in the field’s standard Computational Geometry Algorithms Library, and so M’Sadoques’ algorithm was developed as a solution.

In addition to two alternate proofs, additional work was done to allow the packing of two objects into a container, again avoiding unbounded sets. The algorithms were implemented in C++ and timings were taken using simple 3D input shapes.

Present at the defense were thesis committee members Drs. Karen Daniels, George Grinstein and Cindy Chen from the Computer Science department, and remotely Dr. Victor Milenkovic from the University of Miami.

The complete thesis may be retrieved from the department’s Technical Report repository. The results of this work will also be presented in the Cutting and Packing stream of the Conference for the International Federation of Operational Research Societies (IFORS 2011) in Melbourne, Australia on July 11.


Image illustrating containment problem. Beyond two shapes, the containment problem is NP-complete.

About this Entry

This page contains a single entry by Martin, Fred published on May 20, 2011 9:08 PM.

Daniels and Ye present at 10th International Symposium on Experimental Algorithms was the previous entry in this blog.

Students demonstrate smart phone applications for Data Communications II is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.

Subscribe to feed Subscribe to this blog's feed