A faster algorithm to compute the visibility map of a 1.5D terrain

Given a 1.5D terrain, i.e., an x-monotone polygonal line in R 2 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...

ver descrição completa

Detalhes bibliográficos
Autor principal: Loffler, Maarten (author)
Outros Autores: Saumell, M. (author), Silveira, Rodrigo (author)
Formato: conferenceObject
Idioma:eng
Publicado em: 2018
Texto completo:http://hdl.handle.net/10773/21971
País:Portugal
Oai:oai:ria.ua.pt:10773/21971