Determining the castability of simple polyhedra

ABSTRACT

A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Such polyhedra can be manufactured easily using two cast parts. Assuming that the cast parts are removed by a single translation each, it is shown that for a simple polyhedron with n vertices, castability can be decided in O(n2logn) time and linear space using a simple algorithm. Furthermore, a more complicated algorithm solves the problem in O(n3/2+&egr;) time and space, for any fixed &egr;>0. In the case where the cast parts are to be removed in opposite directions, a simple O(n2) time algorithm is presented. Finally, if the object is a convex polyhedron and the cast parts are to be removed in opposite directions, a simple O(nlog2n) algorithm is presented.

REFERENCES

• 1: Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.517-526, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129763]
• 2: Agarwal, P. K., and M. Sharir, Applications of a new space partitioning technique. Proc. 2nd WADS (1991), Lect. Notes in Comp. Science 519, Springer- Verlag, pp. 379-391.
• 3: Boudewijn Asberg , Gregoria Blanco , Prosenjit Bose , Jesus Garcia-Lopez , Mark H. Overmars , Godfried T. Toussaint , Gordon T. Wilfong , Binhai Zhu, Feasability of Design in Stereolithography, Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.228-237, December 15-17, 1993
• 4: Bose, P., D. Bremner, and M. van Kreveld, Determining the Castability of Simple Polyhedra. Tech. Rep. SOCS 93.12, School of Comp. Science, McGiU University, 1993.
• 5: Prosenjit Bose , Marc J. van Kreveld , Godfried T. Toussaint, Filling Polyhedral Molds, Proceedings of the Third Workshop on Algorithms and Data Structures, p.210-221, August 11-13, 1993
• 6: Bose, P., and G. Toussaint, Geometric and computational aspects of injection molding. Proc. 3rd Int. Conf. on CAD and Computer Graphics (1993), Beijing, China, pp. 237-242. Also: Tech. Rep. SOCS 92.16, School of Comp. Science, McGill University, 1992.
• 7: Bernard Chazelle , Micha Sharir , Emo Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Proceedings of the sixth annual symposium on Computational geometry, p.23-33, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98532]
• 8: Personal Communication with R. Connolly, Manager Injection Molding, Industrial Materials institute, National Research Council of Canada, Boucherville, Quebec, November 1993.
• 9: De Berg, M., personal communication, 1994.
• 10: Dobkin, D. P., and D. G. Kirkpatrick, A linear time algorithm for determining the separation of convex polyhedra. J. of Algorithms 6 (1985), pp. 381-392.
• 11: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 12: Elliott, R., Cast iron technology. Butterworths, London, 1988.
• 13: Fekete, S.P., and J.S.B. Mitchell, Geometric aspects of injection molding, manuscript, 1993.
• 14: Martin Held, On the computational geometry of pocket machining, Springer-Verlag New York, Inc., New York, NY, 1991
• 15: Jiří Matoušek, Efficient partition trees, Proceedings of the seventh annual symposium on Computational geometry, p.1-9, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109649]
• 16: Jiří Matoušek, Range searching with efficient hierarchical cuttings, Proceedings of the eighth annual symposium on Computational geometry, p.276-285, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142732]
• 17: McAllister, M., and J. Snoeyink, Two dimensional Computation of the Three dimensional Reachable Region for a Welding Head. Proc. 5th Canadian Conf. on Comp. Geom (1993), pp. 437-442.
• 18: Megiddo, N., Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comp. 12 (1983), pp. 759-776.
• 19: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 20: Pribble, W.I., Molds for reaction injection, structural foam and expandable styrene molding. In: Plastics mold engineering handbook, J.H. DuBois and W.I. Pribble (Eds.), Van Nostrand Reinhold Company Inc., New York, 1987.
• 21: Rappaport, D., and A. Rosenbloom, Moldable and Castable Polygons. Proc. Jth Canadian Conf. on Comp. Geom. (1992), pp. 322-327.
• 22: M. Reichling, On the detection of a common intersection of k convex objects in the plane, Information Processing Letters, v.29 n.1, p.25-29, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90127-5]
• 23: Walton, C.F., and T.J. Opar (Eds.), iron castings handbook. Iron casting society, Inc., 1981.
• 24: Whelan, A., Injection moulding machines. Elsevier, London, 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided manufacturing (CAM)

General Terms:
Algorithms, Theory