کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414314 680885 2008 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On realistic terrains
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On realistic terrains
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 41, Issues 1–2, October 2008, Pages 48-67