A Faster Algorithm to Compute the Visibility Map of a 1.5D Terrain

Maarten Löffler, Maria Saumell, Rodrigo I. Silveira

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

    Abstract

    Given a 1.5D terrain, i.e., an x-monotone polygonal line in R2 with n vertices, and 1 _< m _< n viewpoints placed on some of the terrain vertices, we study the problem of computing the parts of the terrain that are visible from at least one of the viewpoints. We present an algorithm that runs in O(n + mlogm) time. This improves over a previous algorithm recently proposed.
    Original languageEnglish
    Title of host publicationProc. 30th European Workshop on Computational Geometry
    Number of pages4
    Publication statusPublished - 2014

    Bibliographical note

    (to appear)

    Keywords

    • CG, TIN

    Fingerprint

    Dive into the research topics of 'A Faster Algorithm to Compute the Visibility Map of a 1.5D Terrain'. Together they form a unique fingerprint.

    Cite this