On realistic terrains
Esther Moet, Marc J. van Kreveld, A. Frank van der Stappen · 2006
We study worst-case complexities of visibility and distance structures on terrains under realistic assumptions on edge length ratios and the angles of the triangles. We show that the visibility map of a point for a realistic terrain with n triangles has complexity Θ(n√n). We also prove that the shortest path between two points p and q on a realistic terrain passes through Θ(√n) triangles, and that the bisector between p and q has complexity O(n √n). We use these results to show that the shortest path map for any point on a realistic terrain has complexity Θ(n√n), and that the Voronoi diagram for any set of m points on a realistic terrain has complexity Ω(n + m√n) and O((n+m)√n). Our results immediately imply more efficient algorithms for computing the various structures on realistic terrains.