With the advent of autonomous robots with two- and three-dimensional scanning capabilities, classical visibility-based exploration methods from computational geometry have gained in practical importance. However, real-life laser scanning of useful accuracy does not allow the robot to scan continuously while in motion; instead, it has to stop each time it surveys its environment. This requirement was studied by Fekete, Klein and N"uchter for the subproblem of looking around a corner, but until now has not been considered for whole polygonal regions. We give the first comprehensive algorithmic study for this important algorithmic problem that combines stationary art gallery-type aspects with watchman-type issues in an online scenario. We show that there is a lower bound of $Omega(sqrt{n})$ on the competitive ratio in an orthogonal polygon with holes; we also demonstrate that even for orthoconvex polygons, a competitive strategy can only be achieved for limited aspect ratio $A$, i.e., for a given lower bound on the size of an edge. Our main result is an $O(log A)$-competitive strategy for simple rectilinear polygons, which is best possible up to constants.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Polygon Exploration with Discrete Vision


    Beteiligte:

    Erscheinungsdatum :

    2007-01-01


    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    004 / 629




    Polygon turning

    Engineering Index Backfile | 1956


    Universe exploration vision

    O'HANDLEY, D. / SWAN, P. / SADEH, W. | AIAA | 1992


    Universe exploration vision

    O'Handley, D. / Swan, P. / Sadeh, W. | NTRS | 1992


    Regular polygon detection

    Barnesi, N. / Loy, G. / Shaw, D. et al. | IEEE | 2005


    Regular Polygon Detection

    Barnes, N. / Loy, G. / Shaw, D. et al. | British Library Conference Proceedings | 2005