Finding minumum area k-gons

D. Eppstein, M.H. Overmars, G. Rote, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    52 Citations (Scopus)


    Given a set P of n points in the plane and a number k, we want to find a polygon ~ with vertices in P of minimum area that satisfies one of the following properties: (1) cK is a convex k-gon, (2) ~ is an empty convex k-gon, or (3) ~ is the convex hull of exactly k points of P. We give algorithms for solving each of these three problems in time O(kn3). The space complexity is O(n) for k = 4 and O(kn 2) for k > 5. The algorithms are based on a dynamic ptogramming approach. We generalize this approach to polygons with minimum perimeter, polygons with maximum perimeter or area, polygons containing the maximum or minimum number of points, polygons with minimum weight (for some weights added to vertices), etc., in similar time bounds.
    Original languageEnglish
    Pages (from-to)45-58
    JournalDiscrete and Computational Geometry
    Issue number1
    Publication statusPublished - 1992


    Dive into the research topics of 'Finding minumum area k-gons'. Together they form a unique fingerprint.

    Cite this