Visibility queries in simple polygons and applications

Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon P. We provide a mechanism for expressing the visibility polygon from a point as the disjoint union of logarithmically many canonical pieces using a quadratic-space data structure. This allows us to report visibility polygons in time proportional to their size, but without the cubic space overhead of earlier methods. The same canonical decomposition can be used to determine visibility within a frustum, or to compute various attributes of the visibility polygon efficiently. By exploring the connection between visibility polygons and shortest path trees, we obtain a kinetic algorithm that can track the visibility polygon as the viewpoint moves along polygonal paths inside P, at a polylogarithmic cost per combinatorial change in the visibility. The combination of the static and kinetic algorithms leads to a space query-time tradeoff for the visibility from a point problem and an output-sensitive algorithm for the weak visibility from a segment problem.

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings
    PublisherSpringer Verlag
    Pages357-367
    Number of pages11
    ISBN (Print)3540653856, 9783540653851
    DOIs
    StatePublished - 1998
    Event9th Annual International Symposium on Algorithms and Computation, ISAAC'98 - Taejon, Korea, Republic of
    Duration: Dec 14 1998Dec 16 1998

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume1533 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other9th Annual International Symposium on Algorithms and Computation, ISAAC'98
    CountryKorea, Republic of
    CityTaejon
    Period12/14/9812/16/98

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Visibility queries in simple polygons and applications'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., Guibas, L. J., Teichmann, M., & Zhang, L. (1998). Visibility queries in simple polygons and applications. In Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings (pp. 357-367). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1533 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-49381-6_38