Entries tagged with “computational geometry” from Computer Science Department News

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.
Associate Professor Karen Daniels and her doctoral student Shu Ye presented their paper “Hierarchical Delaunay Triangulation for Meshing” at the 10th International Symposium on Experimental Algorithms in May 2011 in Greece.

Their paper discusses an elliptical pad structure and its polygonal approximation. The elliptical pad is a part of via model structures, which are critical components on today’s multilayered Printed Circuit Board (PCB) and electrical packaging.

To explore meshing characterization of the elliptical pad helps mesh generation over 3D structures for electromagnetic modeling and simulation on PCB and electrical packaging. Because elliptical structures are often key PCB features, the authors introduce a hierarchical mesh construct and show that it has several useful quality characteristics related to Delaunay triangulation.

The Delaunay triangulation has the important modeling characteristic that the minimum triangle angle is maximized.

Daniels and Ye then show experimentally that the Computational Geometry Algorithm Library’s meshing of an elliptical structure at different resolution levels and with various aspect ratios produces patterns similar to the hierarchical construct. In particular, the experiment also shows that the result of meshing is not only a constrained Delaunay triangulation, which preserves the segments that approximate the elliptical structure, but, significantly, it is also a Delaunay triangulation.

A copy of the paper may be downloaded here.


Examples of hierarchical Delaunay triangulations.

Subscribe to feed Subscribe to this blog's feed

Subscribe to feed Search results matching “computational geometry”