Rotational polygon containment and minimum enclosure

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Rotational polygon containment and minimum enclosure

Full text

Pdf (1.10 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the fourteenth annual symposium on Computational geometry table of contents

Minneapolis, Minnesota, United States

Pages: 1 - 8

Year of Publication: 1998

ISBN:0-89791-973-4

Author

Victor J. Milenkovic

University of Miami, Department of Mathematics and Computer Science

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 31, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276884.276885 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. Agarwal, N. Amenta, and M. Sharir. Largest placement of one conve:# polygon inside another. In Proceedings of the Second Workshop on Algorithmic Founda. tions of Robotics, July 1996.
	2	P.K. Agarvral, B. Aronov, and M. Sharir. Motion planning for a convex polygon in a polygonal environment. in preparation., 1992.
	3	F. Avnaim. Placement et dgplacement de formes rigides ou articul#es. Phi) thesis, Universit# de Franche- Comte, France, 1989.
	4	Francis Avnaim , Jean-Daniel Boissonnat, Polygon Placement Under Translation and Rotation, Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science, p.322-333, February 11-13, 1988
	5	C. Bounsaythip and S. Maouche. Irregular shape nesting and placing with evolutionary approach. In 1997 IEEB International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation (Cat. No.97CH86088-5, page 5. IEEE; New York, NY, USA, 12-15 October 1997.
	6	B. Chazelle. The Polygon Containment Problem. In Preparata, editor, Advances in Computing Research, Volume 1: Computational Geometry, pages 1-33. JAI Press, Inc., Greenwich, Connecticut, 1983.
	7	Karen Mcintosh Daniels , Victor J. Milenkovic, Containment algorithms for nonconvex polygons with applications to layout, 1995
	8	Karen Daniels , Victor Milenkovic, Column-Based Strip Packing Using Ordered and Compliant Containment, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.91-107, May 27-28, 1996
	9	K. Daniels and V. J. Milenkovic. Multiple Translational Containment, Part I: An Approx#unate Algorithm. AI- 9orithmiea, 19:148-182, 1997.
	10	K. A. Dowsland and W. B. Dowsland. Packing Problems. European Journal of Operational Research, 55:2 - 14, 1992.
	11	K.A. Dowsland and W.B. Dowsland. Solution approaches to irregular nesting problems. European Journal of Operational Research, 84(3):506--21, Aug#ast 1995.
	12	H. Dyckhoff. A typology of cutting and packing problems. European Journal of Operations Research, 44:145-159, 1990.
	13	R. M. S. Abd EI-Aal. A new technique for nesting irregular shapes based on rectangular modules. Current Advances in Mechanical Design and Production 1996, 6:533--540, 1996.
	14	D. H. Greene and F. F. Yao. Finite-resolution computational geometr3: In Prec. 27th Annu. IEEE Sympos. Found. Comput. Sci., pages 143-152, 1986.
	15	R. Grinde and T. Cavalier. Containment of a Single Polygon Using Mathematical Programming. Tec2mical Report IMSE Working Paper 92-164, The Penusyl#-ania State University, Department of Industrial and Management Systems Engineering, 1993.
	16	Roger B. Grinde , Tom M. Cavalier, A new algorithm for the two-polygon containment problem, Computers and Operations Research, v.24 n.3, p.231-251, March 1997 [doi>10.1016/S0305-0548(96)00050-0]
	17	Leonidas J. Guibas , David H. Marimont, Rounding arrangements dynamically, Proceedings of the eleventh annual symposium on Computational geometry, p.190-199, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220300]
	18	G. C. Han and S. J. Na. Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing. Journal of Engineering Manufacture, 210(B6):509-19, 1996.
	19	Ralf Heckmann , Thomas Lengauer, Computing Upper and Lower Bounds on Textile Nesting Problems, Proceedings of the Fourth Annual European Symposium on Algorithms, p.392-405, September 25-27, 1996
	20	Khoi Hoang. Aspects in automatic nesting of irregular shapes. In Prec. SPIE- Int. Soc. Opt. Eng. (USA), Proceedings of the SPIE- The International Society for Optical Engineering, voi.2589, pages 234--41. SPIE-Int. Soc. Opt. Eng, 23-26 October 1995.
	21	P. Jain, P. Fenyes, and R. Richter. Optimal blank nesting using simulated annealing. Journal of mechanical design, 114(1):160-165, March 1992.
	22	H. J. Lamousin, W. N. Waggenspack, and G. T. Dobson. Nesting of complex 2-d parts within irregular boundaries. Journal of Mechanical Design, 118(4):615, 1996.
	23	Zhenyu Li, Compaction algorithms for non-convex polygons and their applications, Harvard University, Cambridge, MA, 1995
	24	Z. Li and V. Milenko#ic. Compaction and separation algorithms for nonconve#x polygons and their applications. E#ropean Journal of Operations Research, 84:539-561, 1995.
	25	V. Milenkovic. Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic. In Prec. 30th Annu. IEEE Sympos. Found. Comput. Sci., pages 500-505, 1989.
	26	V. Milenkovic. Rounding face lattices in the plane. In Abstracts 1st Canad. Conf. Comput. Geom., page 12, 1989.
	27	Victor J. Milenkovic, Translational polygon containment and minimal enclosure using linear programming based restriction, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.109-118, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237840]
	28	V. Milenkovic and K. Daniels. Translational polygon containment and minimal enclosure using geometric algorithms and mathematical programming. Technical Report 25-95, Center for Research in Computing Technology, Division of Applied Sciences, Harvard University, Cambridge, MA, 1995.
	29	V. J. Milenkovic. Multiple Translational Containment# Part II: Exact Algorithms. Algorithmica# 19:183-218# 1997.
	30	Victor J. Milenkovic. Practical methods for set operatious on polygons using exact arithmetic. In Prec. 7th Canad. Conf. Comput. Geom., pages 55-60, 1995.
	31	Victor J. Milenkovic. Shortest path rounding. Algorithmica, page (submitted), 1997.
	32	Victor J. Milenkovic, Rotational polygon overlap minimization and compaction, Computational Geometry: Theory and Applications, v.10 n.4, p.305-318, July 1, 1998 [doi>10.1016/S0925-7721(98)00012-1]
	33	V.J. Milenkovic and K. Daniels. Translational Polygon Containment and Minimal Enclosure using Mathematical Programming. International Transactions in Operational Research (accepted with revisions), 1997.
	34	Y. K. D. V. Prasad, A set of heuristic algorithms for optimal nesting of two-dimensional irregularly shaped sheet-metal blanks, Computers in Industry, v.24 n.1, p.55-70, May 1994 [doi>10.1016/0166-3615(94)90008-6]
	35	Y.K.D.V. Prasad, S. Somasundaram, and K.P. Rao. A sliding algorithm for optimal nesting of arbitrarily shaped sheet metal blanks. International Journal of Production Research, 33(6):1505-20, June 1995.
	36	P.E. Sweeney and E. R. Paternoster. Cutting and Packing Problems: A Categorized, Application-Oriented Research Bibliography. Journal of the Operational Research Society, 43(7):691-706, 1992.
	37	J. Y. Wang, D. Y. Liu, E. W. Lee, and T. H. Koh. An algorithm for nesting patterns in apparel. In COMPUTER INTEGRATED MANUFA CT#IRING - INTERNATIONAL CONFERENCE- WORLD SCI. ENTIFIC I995; VOL 1, pages 377-384. World Scientific; 1995, 1995.
	38	P.F. Whelan and B.G. Batchelor. Automated packing systems: review of industrial implementations. In Proceedings of the SPIE. The International Society for Optical Engineering, voI.206#, pages 358-69. SPIE# September 1993.

CITED BY 9

	P. V. Sander , Z. J. Wood , S. J. Gortler , J. Snyder , H. Hoppe, Multi-chart geometry images, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Alejo Hausner, Simulating decorative mosaics, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.573-580, August 2001
	Pedro V. Sander , John Snyder , Steven J. Gortler , Hugues Hoppe, Texture mapping progressive meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.409-416, August 2001
	Emil Praun , Adam Finkelstein , Hugues Hoppe, Lapped textures, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.465-470, July 2000
	Takeo Igarashi , Dennis Cosgrove, Adaptive unwrapping for interactive texture painting, Proceedings of the 2001 symposium on Interactive 3D graphics, p.209-216, March 2001
	Eugene Zhang , Konstantin Mischaikow , Greg Turk, Feature-based surface parameterization and texture mapping, ACM Transactions on Graphics (TOG), v.24 n.1, p.1-27, January 2005
	Kai Hormann , Bruno Lévy , Alla Sheffer, Mesh parameterization: theory and practice Video files associated with this course are available from the citation page , ACM SIGGRAPH 2007 courses, August 05-09, 2007, San Diego, California
	Alla Sheffer , Emil Praun , Kenneth Rose, Mesh parameterization methods and their applications, Foundations and Trends® in Computer Graphics and Vision, v.2 n.2, p.105-171, January 2006
	Kai Hormann , Konrad Polthier , Alia Sheffer, Mesh parameterization: theory and practice, ACM SIGGRAPH ASIA 2008 courses, p.1-87, December 10-13, 2008, Singapore