We study generalizations of convex hulls to polygonal domains with holes. Convexity in Euclidean space is based on the notion of shortest paths, which are straight-line segments. In a polygonal domain, shortest paths are polygonal paths called geodesics. One possible generalization of convex hulls is based on the "rubber band" conception of the convex hull boundary as a shortest curve that encloses a given set of sites. However, it is NP-hard to compute such a curve in a general polygonal domain. Hence, we focus on a different, more direct generalization of convexity, where a set X is geodesically convex if it contains all geodesics between every pair of points x,y in X. The corresponding geodesic convex hull presents a few surprises, and turns out to behave quite differently compared to the classic Euclidean setting or to the geodesic hull inside a simple polygon. We describe a class of geometric objects that suffice to represent geodesic convex hulls of sets of sites, and characterize which such domains are geodesically convex. Using such a representation we present an algorithm to construct the geodesic convex hull of a set of O(n) sites in a polygonal domain with a total of n vertices and h holes in O(n^3h^{3+epsilon}) time, for any constant epsilon > 0.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Convex Hulls in Polygonal Domains


    Beteiligte:
    Barba, Luis (Autor:in) / Hoffmann, Michael (Autor:in) / Korman, Matias (Autor:in) / Pilz, Alexander (Autor:in)

    Erscheinungsdatum :

    2018-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    004 / 629




    Optimal Design for Uncertain Load Cases Using Convex Hulls

    Dube, Ravi / Hansen, Jorn | AIAA | 2006


    Optimal Design for Uncertain Load Cases Using Convex Hulls

    Dube, R. / Hansen, J. / American Institute of Aeronautics and Astronautics | British Library Conference Proceedings | 2006


    Convex hulls, occluding contours, aspect graphs and the Hough transform

    Wright, M. / Fitzgibbon, A. / Giblin, P. J. et al. | British Library Online Contents | 1996


    A Simulative Comparison of Ship Domains and Their Polygonal Approximations

    Rafal Szlapczynski / Joanna Szlapczynska | DOAJ | 2015

    Freier Zugriff

    Projective Visual Hulls

    Lazebnik, S. / Furukawa, Y. / Ponce, J. | British Library Online Contents | 2007