On realistic terrains |
| |
Authors: | Esther Moet Marc van Kreveld A. Frank van der Stappen |
| |
Affiliation: | aDepartment of Information and Computing Sciences, Universiteit Utrecht, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands |
| |
Abstract: | 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, and a more general low-density assumption. We show that the visibility map of a point for a realistic terrain with n triangles has complexity . We also prove that the shortest path between two points p and q on a realistic terrain passes through triangles, and that the bisector of p and q has complexity . We use these results to show that the shortest path map for any point on a realistic terrain has complexity , and that the Voronoi diagram for any set of m points on a realistic terrain has complexity and . Our results immediately imply more efficient algorithms for computing the various structures on realistic terrains. |
| |
Keywords: | Realistic input model Polyhedral terrain Visibility maps Shortest path Voronoi diagram |
本文献已被 ScienceDirect 等数据库收录! |
|