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 -