DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Sixty seven
TITLE: "Geometric and Algorithmic Aspects of Computer-Aided Design and Manufacturing"
EDITORS: Ravi Janardan, Michiel Smid, and Debasis Dutta

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.

PREFACE

Computer-Aided Design and Manufacturing (CAD/CAM) is concerned with all aspects of the process of designing, prototyping, manufacturing, inspecting, and maintaining complex geometric objects under computer control. As such, there is a natural synergy between this field and Computational Geometry (CG), which involves the design, analysis, implementation, and testing of efficient algorithms and data representation techniques for geometric entities such as points, polygons, polyhedra, curves, and surfaces. On the one hand, CG can bring about significant performance improvements in CAD/CAM, while, on the other hand, CAD/CAM can be a rich source of interesting problems that can spur new research in CG. Indeed, such two-way interaction has already been witnessed in recent years in areas such as numerically-controlled machining, casting and injection molding, rapid prototyping and layered manufacturing, metrology, and mechanism/linkage design, to name just a few.

To further promote the interaction between the two fields, we organized a Workshop on "Computer-Aided Design and Manufacturing" at the DIMACS Center in Piscataway, NJ, from Oct. 7-9, 2003. The Workshop, which was attended by about fifty-five individuals from academia, research laboratories, and industry, was organized around a series of invited talks, contributed presentations, and informal discussions geared towards fostering collaborative research. Details about the Workshop can be found at http://dimacs.rutgers.edu/archive/Workshops/CompAided/.

Subsequently, authors of papers presented at the Workshop were invited to submit expanded and polished versions of their research to this Volume. The intent was to provide, in one place, a set of self-contained papers that could serve as the starting point for further research. All submissions were refereed. The papers in this Volume are an outgrowth of this process and cover topics such as geometric modeling, computational topology, computational metrology, geometric constraint solving, part immobilization, geometric aspects of machining, layered manufacturing, and algebraic methods.

We thank Fred Roberts (DIMACS Director) and Steve Fortune (Member, DIMACS Executive Council) for their support and encouragement, DIMACS and AMS staff members for organizational help, the referees for their help with the reviews, and, of course, the authors for their research contributions. We are grateful to the National Science Foundation for financial support for the Workshop.

Ravi Janardan (Minneapolis, MN)
Michiel Smid (Ottawa, Canada)
Debasish Dutta (Ann Arbor, MI)
July 2004

TABLE OF CONTENTS


Contents

Forward                                             vii
Preface                                              ix

A Survey of Subdivision-Based Tools for Surface
   Modeling
     I. Boier-Martin, D. Zorin, and F. Bernardini     1

Sample Based Geometric Modeling
     T. Dey                                          29

Computational Topology and Swept Volumes
     D. Blackmore, Y. Mileyko, M. Leu, W. Regli,
        and W. Sun                                   53

Elements of Computational Metrology
     V. Srinivasan                                   79

Combinatorial Approaches to Geometric Constraint
   Solving: Problems, Progress, and Directions
     M. Sitharam                                    117

Immobilization: Analysis, Existence, and Output-
   Sensitive Synthesis                              
     F. van der Stappen                             165

Geometric Algorithms for Layered Manufacturing
     R. Janardan and M. Smid                        189

Towards a Process Planning Framework for Multi-
   Direction Layered Deposition
     P. Singh and D. Dutta                          221

Machinability: Geometric Reasoning for Cutting
     T. Kim and S. Sarma                            245

Zig-Zag Tool Path Generation for Sculptured Surface
   Finishing
     D. Misra, V. Sundararajan and P. Wright        265

Implicitization Exploiting Sparseness
     I. Emiris and I. Kotsireas                     281

The Exact Rational Univariate Representation for
   Detecting Degeneracies
     J. Keyser, K. Ouchi and J.M. Rojas             299

Mass Properties of the Union of Millions of
   Identical Cubes
     W.R. Franklin                                  329
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on July 19, 2005.