On minimum-area hulls

E. M. Arkin, Y. J. Chiang, M. Held, J. S.B. Mitchell, V. Sacristan, S. S. Skiena, T. C. Yang

    Research output: Contribution to journalArticle

    Abstract

    We study some minimum-area hull problems that generalize the notion of convex hull to star-shaped and monotone hulls. Specifically, we consider the minimum-area star-shaped hull problem: Given an n-vertex simple polygon P, find a minimum-area, star-shaped polygon P* containing P. This problem arises in lattice packings of translates of multiple, nonidentical shapes in material layout problems (e.g., in clothing manufacture), and has been recently posed by Daniels and Milenkovic. We consider two versions of the problem: the restricted version, in which the vertices of P* are constrained to be vertices of P, and the unrestricted version, in which the vertices of P* can be anywhere in the plane. We prove that the restricted problem falls in the class of "3SUM-hard" (sometimes called "n2-hard") problems, which are suspected to admit no solutions in o(n2) time. Further, we give an O(n2) time algorithm, improving the previous bound of O(n5). We also show that the unrestricted problem can be solved in O(n2p(n)) time, where p(n) is the time needed to find the roots of two equations in two unknowns, each a polynomial of degree O(n). We also consider the case in which P* is required to be monotone, with respect to an unspecified direction; we refer to this as the minimum-area monotone hull problem. We give a matching lower and upper bound of Θ(n log n) time for computing P* in the restricted version, and an upper bound of O(nq(n)) time in the unrestricted version, where q(n) is the time needed to find the roots of two polynomial equations in two unknowns with degrees 2 and O(n).

    Original languageEnglish (US)
    Pages (from-to)119-136
    Number of pages18
    JournalAlgorithmica (New York)
    Volume21
    Issue number1
    DOIs
    StatePublished - 1998

    Keywords

    • 3SUM-Hardness
    • Computational geometry
    • Design and analysis of algorithms
    • Lower bounds
    • Minimum-area hulls
    • Monotone polygons
    • Star-shaped polygons

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'On minimum-area hulls'. Together they form a unique fingerprint.

  • Cite this

    Arkin, E. M., Chiang, Y. J., Held, M., Mitchell, J. S. B., Sacristan, V., Skiena, S. S., & Yang, T. C. (1998). On minimum-area hulls. Algorithmica (New York), 21(1), 119-136. https://doi.org/10.1007/PL00009204