Finding minimal convex nested polygons

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding minimal convex nested polygons

Full text

Pdf (624 KB)

Source

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

Baltimore, Maryland, United States

Pages: 296 - 304

Year of Publication: 1985

ISBN:0-89791-163-6

Authors

Alok Aggarwal	Mathematical Science Department, IBM Research Center, Yorktown Heights, New York
Heather Booth	Department of Rlectrical Engineering and Computer Science, The Johns Hopkins University, Baltimore MD
Joseph O'Rourke	Department of Rlectrical Engineering and Computer Science, The Johns Hopkins University, Baltimore MD
Subhash Suri	Department of Rlectrical Engineering and Computer Science, The Johns Hopkins University, Baltimore MD
Chee K. Yap	Courant Institute of Mathematical Sciences, 251 Mcrce Street, New York, NY

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): 3, Downloads (12 Months): 31, Citation Count: 5

Additional Information:

abstract 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/323233.323271 What is a DOI?

ABSTRACT

We consider the problem of finding a polygon nested between two given convex polygons that has a minimal number of vertices. Our main result is an &Ogr;(nlog&kgr;) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and &kgr; is the number of vertices of a minimal nested polygon. We also present an &Ogr;(n) sub-optimal algorithm, and a simple &Ogr;(nk) optimal algorithm.

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	[CY] J. S. Chang and C. K. Yap. "A Polynomial Solution for Potato-Peeling and Other Polygon Inclusion and Enclosure Problems," Foundations of Computer Science, pp. 408-417 (1984).
	2	[DA] N. A. A. De Pano and A. Aggarwal. "Finding Restricted k-envelopes For Convex Polygons," Proc. 22nd Allerton Conference, pp. 81-90 (1984).
	3	[DB] B. Dori and M. Ben-Bassat, "Circumscribing a Convex Polygon by a Polygon of fewer sides with Minimum Area Addition," Computer Vision, Graphics and Image Processing, 24 pp. 131-159 (1983).
	4	[KL] V. Klee and M. C. Laskowski, "Finding the Smallest Triangle Containing a Given Convex Polygon," J. of Algorithms, to appear (1985).
	5	[OR] J. O'Rourke, "Finding Minimal Enclosing Boxes," The Johns Hopkins University, Tech. Rep. (1984).
	6	[SO] S. Suri and J. O'Rourke, "Finding Minimal Nested Polygons," The Johns Hopkins University, Tech. Rep. (1985).
	7	[To] G. Toussaint, "Solving Geometric Problems with Rotating Calipers," Proc. IEEE MELECON '83, (May 1983).

CITED BY 5

	C Wang , E P F Chan, Finding the minimum visible vertex distance between two non-intersecting simple polygons, Proceedings of the second annual symposium on Computational geometry, p.34-42, June 02-04, 1986, Yorktown Heights, New York, United States
	Kasturi R. Varadarajan, Approximating monotone polygonal curves using the uniform metric, Proceedings of the twelfth annual symposium on Computational geometry, p.311-318, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Michael T. Goodrich, Efficient piecewise-linear function approximation using the uniform metric: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.322-331, June 06-08, 1994, Stony Brook, New York, United States
	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
	Christian Ronse, A Bibliography on Digital and Computational Convexity (1961-1988), IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.181-190, February 1989