New algorithms for minimum area k-gons

ABSTRACT

Given a set P of n points in the plane, we wish to find a set Q ⊂ P of k points for which the convex hull conv(Q> has the minimum area. We solve this, and the related problem of finding a minimum area convex k-gon, in time O(n2 log n) for fixed k, almost matching known bounds for the minimum area triangle problem. Our algorithm is based on finding a certain number of nearest vertical neighbors to each line segment determined by two input points. We use a classical result of Ramsey theory to prove that these nearest neighbors suffice to determine the minimum convex k-gon.

REFERENCES

• 1: A. Aggarwal , H. Imai , N. Katoh , S. Suri, Fining k points with minimum spanning trees and related problems, Proceedings of the fifth annual symposium on Computational geometry, p.283-291, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73865]
• 2: A. Aggarwal, M.M. Klawe, S. Moran, P. Shor and R. Wilber. Geometric applications of eL matrix-searching algorithm. Algorithmica 2 (1987) 195-208.
• 3: David Avis , David Rappaport, Computing the largest empty convex subset of a set of points, Proceedings of the first annual symposium on Computational geometry, p.161-167, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323255]
• 4: James E. Boyce , David P. Dobkin , Robert L. Drysdale, III , Leo J. Guibas, Finding extremal polygons, SIAM Journal on Computing, v.14 n.1, p.134-147, Feb. 1985 [doi>10.1137/0214011]
• 5: D.P. Dobkin, R.L. Drysdale and L.J. Guibas. Finding smallest polygons. Adv. Computing Research, Vol. 1, JAI Press (1983) 181-214.
• 6: D. P. Dobkin , H. Edelsbrunner , M. H. Overmars, Searching for empty convex polygons, Proceedings of the fourth annual symposium on Computational geometry, p.224-228, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73416]
• 7: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• 8: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 9: D. Eppstein. Iterated nearest neighbors and finding minimal polygons. Manuscript, 1991.
• 10: D. Eppstein and J. Erickson. Finding small convex polytopes. Manuscript, 1991.
• 11: David Eppstein , Mark Overmars , Günter Rote , Gerhard Woeginger, Finding minimum area k-gons, Discrete & Computational Geometry, v.7 n.1, p.45-58, 1992 [doi>10.1007/BF02187823]
• 12: P. ErdSs and G. Szekeres. A combinatorial problem in geometry. Compositio Math. 2 (1935) 463-470.
• 13: M.L. Fredman and D.E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. 3Ist IEEE Syrup. Found. Computer Sc,ence (1990) 719-725.
• 14: R.L. Graham, B.L. Rothschild, and J.H. Spencer. Ramsey Theory. Wiley, 1980.
• 15: J.D. Horton. Sets with no empty convex 7-gons. Uanad. Math. Bull. 26 (1983) 482-484.
• 16: M.I-I. Overmars, B. Scholten ~nd I. Vincent. Sets without empty convex 6-gons. Bull. EATCS 37 (1989) 160.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Theory, Verification