Translational polygon containment and minimal enclosure using linear programming based restriction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Translational polygon containment and minimal enclosure using linear programming based restriction

Full text

Pdf (1.14 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 109 - 118

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Victor J. Milenkovic

University of Miami, Department of Math and Computer Science

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 17, Citation Count: 5

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/237814.237840 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	F. Avnaim. Placement et ddplacement de formes rigides ou articul~es. PhD thesis, Universit6 de Franche-Cornt/!, France, 1989.
	2	F. Avnaim , J. Bsissonnat, Simultaneous containment of several polygons, Proceedings of the third annual symposium on Computational geometry, p.242-247, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41984]
	3	Karen Mcintosh Daniels , Victor J. Milenkovic, Containment algorithms for nonconvex polygons with applications to layout, 1995
	4	K. Daniels and V. J. Milenkovic. Multiple Translational Containment, Part I: An Approximate Algorithm. Aloorithmica, special issue on Computational Geometry in Manufacturing, accepted, subject to revisions.
	5	Karen Daniels , Victor J. Milenkovic, Multiple translational containment: approximate and exact algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.205-214, January 22-24, 1995, San Francisco, California, United States
	6	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
	7	K. Daniels, V. J. Milenkovic, and Z. Li. Multiple Containment Methods. Technical Report 12-94, Center for Research in Computing Technology, Division of Applied Sciences, Harvard University, 1994.
	8	O. Devillers. Simultaneous Containment of Several Polygons: Analysis of the Contact Configurations. Technical Report 1179, INRIA, 1990.
	9	K. A. Dowsland and W. B. Dowsland. Packing Problems. Eu. ropean Journal of Operational Research, 56:2 - 14, 1992.
	10	H. Dyckhoff. A typology of cutting and packing problems. European Jour~al of Operations Research, 44:145-159, 1990.
	11	Steven Fortune, A Fast Algorithm for Polygon Containment by Translation (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.189-198, July 15-19, 1985
	12	L. Guibas, L. Ramshaw, and j. Stolfi. A Kinetic Framework for Computational Geometry. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 100- 111, 1983.
	13	A. Kaul, M.A. O'Connor, and V. Srinivasan. Computing Minkowski Sums of Regular Polygons. In Proceedings of the 3rd Canadian Conference on Computational Geometry, Vancouver, British Columbia, 1991.
	14	Zhenyu Li, Compaction algorithms for non-convex polygons and their applications, Harvard University, Cambridge, MA, 1995
	15	V. J. Milenkovic. Exact Algorithms for Multiple Containment. Algorithmica, special issue on Computational Geometry in Manufacturing, accepted, subject to revisions.
	16	V. J. 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, 1995.
	17	P. E. Sweeney and E. R. Paternoster. Cutting and Packing Problems: A Categorized, Application-Oriented Research Bibliography. Jour~al of the Operational Research Society, 43(7):691- 706, 1992.

CITED BY 5

	Victor J. Milenkovic, Rotational polygon containment and minimum enclosure, Proceedings of the fourteenth annual symposium on Computational geometry, p.1-8, June 07-10, 1998, Minneapolis, Minnesota, United States
	Nancy M. Amato, Equipping CAD/CAM systems with geometric intelligence, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
	Victor J. Milenkovic, Rotational polygon overlap minimization, Proceedings of the thirteenth annual symposium on Computational geometry, p.334-343, June 04-06, 1997, Nice, France
	Victor J. Milenkovic, Densest translational lattice packing of non-convex polygons (extended abstract), Proceedings of the sixteenth annual symposium on Computational geometry, p.280-289, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Danny Z. Chen , Xiaobo Hu , Yingping Huang , Yifan Li , Jinhui Xu, Algorithms for congruent sphere packing and applications, Proceedings of the seventeenth annual symposium on Computational geometry, p.212-221, June 2001, Medford, Massachusetts, United States