کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10327427 | 681040 | 2013 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounded-degree polyhedronization of point sets
ترجمه فارسی عنوان
چند ضلعی سازی مجموعه های نقطه ای محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
سرپانتین، تتردررژی، پوست کنده کاغذ بسته بندی هدیه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In 1994 Grünbaum showed that, given a point set S in R3, it is always possible to construct a polyhedron whose vertices are exactly S. Such a polyhedron is called a polyhedronization of S. Agarwal et al. extended this work in 2008 by showing that there always exists a polyhedronization that can be decomposed into a union of tetrahedra (tetrahedralizable). In the same work they introduced the notion of a serpentine polyhedronization for which the dual of its tetrahedralization is a chain. In this work we present a randomized algorithm running in O(nlog6n) expected time which constructs a serpentine polyhedronization that has vertices with degree at most 7, answering an open question by Agarwal et al.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 2, February 2013, Pages 148-153
Journal: Computational Geometry - Volume 46, Issue 2, February 2013, Pages 148-153
نویسندگان
Gill Barequet, Nadia Benbernou, David Charlton, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schulz, Diane L. Souvaine, Godfried T. Toussaint, Andrew Winslow,