TY - GEN

T1 - Filling polyhedral molds

AU - Bose, Prosenjit

AU - Van Kreveld, Marc

AU - Toussaint, Godfried

N1 - Funding Information:
A well-known technique used in the manufacturing of goods is injection molding. A mold, as defined in \[3\],r efers to the whole assembly of parts that make up a cavity into which liquid is poured to give the shape of the desired component when the liquid hardens. Given a mold (modeled as a polyhedron), establishing whether there exists an orientation that allows the filling of the mold using oitly one pin gate (the pin gate is the point from which the liquid is injected into the mold) as well as determining an orientation that allows the most complete fill are two major problems in the field of injection molding. These problems seem difficult and to date only heuristics have been proposed as solutions to these two problems \[3, 10, 17\]. In fact, until now, determining the favorable position for filling a mold was considered a cut-and-try process \[17\]. An initial study of the geometric and computational aspects of mold filling in two dimensions has been carried out by Bose and Toussalnt \[2\],w ho show that for any mold modeled by a simple polygon P with n vertices, one can decide in O(n) time whether a given orientation allows for a complete fill (the point from which a polygon is filled is always the highest point with respect to the direction of gravity). They also presented a linear time algorithm that determines whether *R esearch supported in part by NSERC PGSB scholarship, an NSERC international fellowship, and NSERC-OGP0009293 and FCAR-93ER0291. School of Computer Science, McGill University, 3480 University St., Montr6al, Qu6bec, Canada H3A 2A7.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1993

Y1 - 1993

N2 - In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after termination of the injection process is an important problem. We study the problem of determining a favorable position of a mold (modeled as a polyhedron), such that when it is filled, no air bubbles and ensuing surface defects arise. Given a polyhedron in a fixed orientation, we present a linear time algorithm that determines whether the mold can be filled from that orientation without forming air bubbles. We also present an algorithm that determines the most favorable orientation for a polyhedral mold in O(n2) time. A reduction from a well-known problem indicates that improving the O(n2) bound is unlikely for general polyhedral molds. But we give an improved algorithm for molds that satisfy a local regularity condition that runs in time O(nk log2n log log(n/k)), where k is the number of local maxima. Finally, we relate fillability to certain known classes of polyhedral.

AB - In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after termination of the injection process is an important problem. We study the problem of determining a favorable position of a mold (modeled as a polyhedron), such that when it is filled, no air bubbles and ensuing surface defects arise. Given a polyhedron in a fixed orientation, we present a linear time algorithm that determines whether the mold can be filled from that orientation without forming air bubbles. We also present an algorithm that determines the most favorable orientation for a polyhedral mold in O(n2) time. A reduction from a well-known problem indicates that improving the O(n2) bound is unlikely for general polyhedral molds. But we give an improved algorithm for molds that satisfy a local regularity condition that runs in time O(nk log2n log log(n/k)), where k is the number of local maxima. Finally, we relate fillability to certain known classes of polyhedral.

UR - http://www.scopus.com/inward/record.url?scp=84934376409&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84934376409&partnerID=8YFLogxK

U2 - 10.1007/3-540-57155-8_249

DO - 10.1007/3-540-57155-8_249

M3 - Conference contribution

AN - SCOPUS:84934376409

SN - 9783540571551

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 210

EP - 221

BT - Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

A2 - Whitesides, Sue

PB - Springer Verlag

T2 - 3rd Workshop on Algorithms and Data Structures, WADS 1993

Y2 - 11 August 1993 through 13 August 1993

ER -