We introduce space-efficient plane-sweep algorithms for basic planar geometric problems. It is assumed that the input is in a read-only array of n items and that the available workspace is Theta(s) bits, where lg n <= s <= n * lg n. Three techniques that can be used as general tools in different space-efficient algorithms are introduced and employed within our algorithms. In particular, we give an almost-optimal algorithm for finding the closest pair among a set of n points that runs in O(n^2 /s + n * lg s) time. We also give a simple algorithm to enumerate the intersections of n line segments that runs in O((n^2 /s^{2/3}) * lg s + k) time, where k is the number of intersections. The counting version can be solved in O((n^2/s^{2/3}) * lg s) time. When the segments are axis-parallel, we give an O((n^2/s) * lg^{4/3} s + n^{4/3} * lg^{1/3} n)-time algorithm that counts the intersections and an O((n^2/s) * lg s * lg lg s + n * lg s + k)-time algorithm that enumerates the intersections, where k is the number of intersections. We finally present an algorithm that runs in O((n^2 /s + n * lg s) * sqrt{(n/s) * lg n}) time to calculate Klee's measure of axis-parallel rectangles.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Space-Efficient Plane-Sweep Algorithms


    Beteiligte:
    Elmasry, Amr (Autor:in) / Kammer, Frank (Autor:in)

    Erscheinungsdatum :

    2016-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    004 / 629




    Multi-plane wing folding and unfolding mechanism with variable sweep angle

    RUAN ZHIYUAN / LU DEKUN / YANG PENGQIAN et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    Variable Sweep

    S. Y. Skripnichenko | NTIS | 1971


    Vector sweep

    Moutrie, C. L. / Oneill, R. F. | NTRS | 1977


    Clean sweep

    Online Contents | 1994


    WING SWEEP OSCILLATION

    MAHAFFEY, P. / HARDING, E. | AIAA | 1970