کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420837 683991 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On polyhedra induced by point sets in space
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On polyhedra induced by point sets in space
چکیده انگلیسی

Given a set S   of n⩾3n⩾3 points in the plane (not all on a line) it is well known that it is always possible to polygonize S, i.e., construct a simple polygon P such that the vertices of P are precisely the given points in S. For example, the shortest circuit through S   is a simple polygon. In 1994, Grünbaum showed that an analogous theorem holds in R3R3. More precisely, if S   is a set of n⩾4n⩾4 points in R3R3 (not all of which are coplanar) then it is always possible to polyhedronize S, i.e., construct a simple (sphere-like) polyhedron P such that the vertices of P are precisely the given points in S. Grünbaum's constructive proof may yield Schönhardt polyhedra that cannot be triangulated. In this paper several alternative algorithms are proposed for constructing such polyhedra induced by a set of points, which may always be triangulated, and which enjoy several other useful properties as well. Such properties include polyhedra that are star-shaped, have Hamiltonian skeletons, and admit efficient point-location queries. We show that polyhedronizations   with a variety of such useful properties can be computed efficiently in O(nlogn)O(nlogn) time. Furthermore, we show that a tetrahedralized, xy-monotonic, polyhedronization of S   may be computed in time O(n1+ε)O(n1+ε), for any ε>0ε>0.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 1, 1 January 2008, Pages 42–54
نویسندگان
, , , ,