The beacon model is a recent paradigm for guiding the trajectory of messages or small robotic agents in complex environments. A beacon is a fixed point with an attraction pull that can move points within a given polygon. Points move greedily towards a beacon: if unobstructed, they move along a straight line to the beacon, and otherwise they slide on the edges of the polygon. The Euclidean distance from a moving point to a beacon is monotonically decreasing. A given beacon attracts a point if the point eventually reaches the beacon. The problem of attracting all points within a polygon with a set of beacons can be viewed as a variation of the art gallery problem. Unlike most variations, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. It is connected and can be computed in linear time for simple polygons. By contrast, it is known that the inverse attraction region of a point - the set of beacon positions that attract it - could have Omega(n) disjoint connected components. In this paper, we prove that, in spite of this, the total complexity of the inverse attraction region of a point in a simple polygon is linear, and present a O(n log n) time algorithm to construct it. This improves upon the best previous algorithm which required O(n^3) time and O(n^2) space. Furthermore we prove a matching Omega(n log n) lower bound for this task in the algebraic computation tree model of computation, even if the polygon is monotone.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    An Optimal Algorithm to Compute the Inverse Beacon Attraction Region


    Beteiligte:

    Erscheinungsdatum :

    2018-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    004 / 629




    An optimal algorithm to compute the inverse beacon attraction region

    Kostitsyna, Irina / Kouhestani, Bahram / Langerman, Stefan et al. | BASE | 2018

    Freier Zugriff

    Region of Attraction with Performance Bounds

    Ganguli, Subhabrata / Ariyur, Kartik / Enns, Dale | AIAA | 2009


    BEACON, BEACON GENERATION METHOD, BEACON GENERATION APPARATUS, AND DEVICE

    CAI JIANCHENG / LIU XINMIN / ZHANG YEXUN et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    Optimal wavelength for Rayleigh laser beacon [5490-114]

    Yan, J. / Xin, Y. / Zhou, C. et al. | British Library Conference Proceedings | 2004


    Beacon

    KIM GI WON / BACK YOUNG SUN / KANG HANG GEUN et al. | Europäisches Patentamt | 2019

    Freier Zugriff