  Given an $n$-vertex 1.5D terrain $\T$ and a set $\A$ of $m<n$ viewpoints, the
Voronoi visibility map $\vorvis(\T,\A)$ is a partitioning of $\T$ into regions
such that each region is assigned to the closest (in Euclidean distance)
visible viewpoint. The colored visibility map $\colvis(\T,\A)$ is a
partitioning of $\T$ into regions that have the same set of visible viewpoints.
In this paper, we propose an algorithm to compute $\vorvis(\T,\A)$ that runs in
$O(n+(m^2+k_c)\log n)$ time, where $k_c$ and $k_v$ denote the total complexity
of $\colvis(\T,\A)$ and $\vorvis(\T,\A)$, respectively. This improves upon a
previous algorithm for this problem. We also generalize our algorithm to higher
order Voronoi visibility maps, and to Voronoi visibility maps with respect to
other distances. Finally, we prove bounds relating $k_v$ to $k_c$, and we show
an application of our algorithm to a problem on limited range of sight.
