Filling polyhedral molds

Prosenjit Bose; Marc Van Kreveld; Godfried Toussaint

doi:10.1007/3-540-57155-8_249

Filling polyhedral molds

Prosenjit Bose, Marc Van Kreveld, Godfried Toussaint

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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(n²) time. A reduction from a well-known problem indicates that improving the O(n²) 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 log²n log log(n/k)), where k is the number of local maxima. Finally, we relate fillability to certain known classes of polyhedral.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides
Publisher	Springer Verlag
Pages	210-221
Number of pages	12
ISBN (Print)	9783540571551
DOIs	https://doi.org/10.1007/3-540-57155-8_249
State	Published - 1993
Event	3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada Duration: Aug 11 1993 → Aug 13 1993

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	709 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd Workshop on Algorithms and Data Structures, WADS 1993
Country	Canada
City	Montreal
Period	8/11/93 → 8/13/93

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-57155-8_249

Fingerprint Dive into the research topics of 'Filling polyhedral molds'. Together they form a unique fingerprint.

Cite this

Bose, P., Van Kreveld, M., & Toussaint, G. (1993). Filling polyhedral molds. In F. Dehne, J-R. Sack, N. Santoro, & S. Whitesides (Eds.), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings (pp. 210-221). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-57155-8_249

Filling polyhedral molds. / Bose, Prosenjit; Van Kreveld, Marc; Toussaint, Godfried.

Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Nicola Santoro; Sue Whitesides. Springer Verlag, 1993. p. 210-221 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bose, P, Van Kreveld, M & Toussaint, G 1993, Filling polyhedral molds. in F Dehne, J-R Sack, N Santoro & S Whitesides (eds), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 709 LNCS, Springer Verlag, pp. 210-221, 3rd Workshop on Algorithms and Data Structures, WADS 1993, Montreal, Canada, 8/11/93. https://doi.org/10.1007/3-540-57155-8_249

Bose P, Van Kreveld M, Toussaint G. Filling polyhedral molds. In Dehne F, Sack J-R, Santoro N, Whitesides S, editors, Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Springer Verlag. 1993. p. 210-221. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-57155-8_249

Bose, Prosenjit ; Van Kreveld, Marc ; Toussaint, Godfried. / Filling polyhedral molds. Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Nicola Santoro ; Sue Whitesides. Springer Verlag, 1993. pp. 210-221 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8715cba2d5e843918db44a10e96e32fb,

title = "Filling polyhedral molds",

abstract = "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.",

author = "Prosenjit Bose and {Van Kreveld}, Marc and Godfried Toussaint",

year = "1993",

doi = "10.1007/3-540-57155-8_249",

language = "English (US)",

isbn = "9783540571551",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "210--221",

editor = "Frank Dehne and Jorg-Rudiger Sack and Nicola Santoro and Sue Whitesides",

booktitle = "Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings",

note = "3rd Workshop on Algorithms and Data Structures, WADS 1993 ; Conference date: 11-08-1993 Through 13-08-1993",

}

TY - GEN

T1 - Filling polyhedral molds

AU - Bose, Prosenjit

AU - Van Kreveld, Marc

AU - Toussaint, Godfried

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 -