Finding extremal polygons

ABSTRACT

Given n points in the plane, we present algorithms for finding maximum perimeter or area convex k-gons with vertices k of the given n points. Our algorithms work in linear space and time O(knlg n + n lg 2n). For the special case k -&-equil; 3 we give O (nlgn) algorithms for these problems. Several related issues are discussed.

REFERENCES

• 1: Dobkin, D. P., and Lipton, R. J. On the Complexity of Computations under Varying Sets of Primitives, J. of Comp. and Syst. Sciences, 18, 1979, 86-91
• 2: Dobkin, D. P., and Snyder, L. On a General Method for Maximizing and Minimizing Among Certain Geometric Problems. Twentieth IEEE Symposium on the Foundations of Computer Science, 1979, 9-17
• 3: Dobkin, D. P., and Munro, I. personal communication
• 4: Dolev, D., and Siegel, A. The Separation for General Single-Layer Wiring Barriers, in VLSI Systems and Computations, Computer Science Press, 1981, 143-152
• 5: Graham, R. L. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set, Info. Proc. Lett., 1, 1972, 132-133
• 6: Horowitz, E., and Sahni, Sartaj Fundamentals of Computer Algorithms, Computer Science Press, 1978
• 7: Iaglom, I. M., and Boltyanskii, V. G. Convex Figures, Holt, Rinehart and Wiriston, 1961
• 8: Post. M. J. A Minimum Spanning Ellipse Algorithm, Twenty-second Annual IEEE Symposium on the Foundations of Computer Science, 1981, 115-122
• 9: Santalo, L. A. Integral Geometry and Geometric Probability, Addison-Wesley, 1976
• 10: Shamos, M. I. Problems in Computational Geometry, Unpublished Manuscript, June 1974. Revised May 1975, Feb. 1977
• 11: Yao, A. C. Fast Algorithms for Minimum Spanning Trees in k Dimensions, Fifteenth Annual Allerton Conference on Communication, Control, and Computing, Sept. 1977, 553-556
• 12: F. Frances Yao, Efficient dynamic programming using quadrangle inequalities, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.429-435, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804691]