کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414626 | 680989 | 2015 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Spiderman graph: Visibility in urban regions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Motivated by the inaccuracy of GPS devices in urban regions, we study the problem of computing the visibility graph of an urban region. Given a scene of buildings, where a building is represented by the set of its walls, the vertices of the graph correspond to the buildings' walls, and there is an edge between two walls if and only if they are weakly visible to each other. We present efficient algorithms for several scenes, including a sophisticated O(n2log2n)O(n2log2n)-time algorithm for a scene consisting of n walls of varying heights parallel to the yz-plane, where visibility is restricted to directions whose projections on the xy-plane are horizontal. This algorithm uses persistent search trees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 3, March 2015, Pages 251–259
Journal: Computational Geometry - Volume 48, Issue 3, March 2015, Pages 251–259
نویسندگان
Paz Carmi, Eran Friedman, Matthew J. Katz,