An algorithm to compute the Minkowski sum outer-face of two simple polygons

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An algorithm to compute the Minkowski sum outer-face of two simple polygons

Full text

Pdf (737 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 234 - 241

Year of Publication: 1996

ISBN:0-89791-804-5

Author

G. D. Ramkumar

Department of Computer Science, Stanford University, Stanford, CA

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): 8, Downloads (12 Months): 45, Citation Count: 0

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/237218.237374 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	J. Basch, L.J. Guibas, G.D. Ramkumar, and L. Ramshaw. Polyhedral tracings and their convolution. Submitted.
	2	Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , John Hershberger , Micha Sharir , Jack Snoeyink, Ray shooting in polygons using Geodesic triangulations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.661-673, June 1991, Madrid, Spain
	3	Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir , Jack Snoeyink, Computing a face in an arrangement of line segments and related problems, SIAM Journal on Computing, v.22 n.6, p.1286-1302, Dec. 1993 [doi>10.1137/0222077]
	4	Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths via balanced geodesic triangulations, Proceedings of the ninth annual symposium on Computational geometry, p.318-327, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161157]
	5	L. J. Guibas, L. Ramshaw, and J. Stolfi. A kinetic framework for computational geometry, in Proc. ~Jth Annu. IEEE Sympos. Found. Cornput. Sci., pages 100-111, 1983.
	6	L. J. Guibas and R. Seidel. Computing convolutions by reciprocal search. Discrete Comput. Geom., 2:175-193, 1987.
	7	Sariel Har-Peled, Timothy M. Chart, Boris Aronov, Dan Halperin, and Jack Snoeyink. The complexity of a single face of a Minkowski sum. In Proc. 7th Canad. Conf. Comput. Geom., pages 91-96, 1995.
	8	A. Kaul, M. A. O'Connor, and V. Srinivasan. Computing Minkowski sums of regular polygons. in Proc. 3rd Canad. Conf. Comput. Geom., pages 74-77, 1991.
	9	T. Lozano-P~rez. Spatial planning: A configuration space approach. IEEE Trans. Comput., C-32:108-120, 1983.

CITED BY 3

	Kokichi Sugihara, Hyperpolygons generated by the invertible Minkowski sum of polygons, Pattern Recognition Letters, v.25 n.5, p.551-560, 5 April 2004
	Maria Lucia Sampoli , Martin Peternell , Bert Jüttler, Rational surfaces with linear normals and their convolutions with rational surfaces, Computer Aided Geometric Design, v.23 n.2, p.179-192, February 2006
	Julia A Bennell , Xiang Song, A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums, Computers and Operations Research, v.35 n.1, p.267-281, January, 2008