A Faster Algorithm to Compute the Visibility Map of a 1.5D Terrain
Maarten Löffler, Maria Saumell, Rodrigo I. Silveira · RECERCAT (Consorci de Serveis Universitaris de Catalunya) · 2014
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.