کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
415389 | 681203 | 2014 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Draining a polygon—or—rolling a ball out of a polygon
ترجمه فارسی عنوان
ریختن یک چند ضلعی؟ یک توپ از یک چند ضلعی؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
چند ضلعی، تخلیه تزریق پر کردن، قالب های چند منظوره
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We introduce the problem of draining water (or balls representing water drops) out of a punctured polygon (or a polyhedron) by rotating the shape. For 2D polygons, we obtain combinatorial bounds on the number of holes needed, both for arbitrary polygons and for special classes of polygons. We detail an O(n2logn) algorithm that finds the minimum number of holes needed for a given polygon, and argue that the complexity remains polynomial for polyhedra in 3D. We make a start at characterizing the 1-drainable shapes, those that only need one hole.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 2, Part C, February 2014, Pages 316–328
Journal: Computational Geometry - Volume 47, Issue 2, Part C, February 2014, Pages 316–328
نویسندگان
Greg Aloupis, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, Joseph OʼRourke,