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 language | English |
---|---|
Title of host publication | Proc. 30th European Workshop on Computational Geometry |
Number of pages | 4 |
Publication status | Published - 2014 |
Bibliographical note
(to appear)Keywords
- CG, TIN