کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9654913 681071 2005 25 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Local polyhedra and geometric graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Local polyhedra and geometric graphs
چکیده انگلیسی
We introduce a new realistic input model for straight-line geometric graphs and nonconvex polyhedra. A geometric graph G is local if (1) the longest edge at every vertex v is only a constant factor longer than the distance from v to its Euclidean nearest neighbor among the other vertices of G and (2) the longest and shortest edges of G differ in length by at most a polynomial factor. A polyhedron is local if all its faces are simplices and its edges form a local geometric graph. We show that any boolean combination of two local polyhedra in Rd, each with n vertices, can be computed in O(nlogn) time using a standard hierarchy of axis-aligned bounding boxes. Using results of de Berg, we also show that any local polyhedron in Rd has a binary space partition tree of size O(nlogd−2n) and depth O(logn); these bounds are tight in the worst case when d⩽3. Finally, we describe efficient algorithms for computing Minkowski sums of local polyhedra in two and three dimensions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 31, Issues 1–2, May 2005, Pages 101-125
نویسندگان
,