کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657737 | 690096 | 2005 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reconstruction of convex polyominoes from orthogonal projections of their contours
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Reconstruction of convex polyominoes from orthogonal projections of their contours Reconstruction of convex polyominoes from orthogonal projections of their contours](/preview/png/9657737.png)
چکیده انگلیسی
The problem of reconstructing a convex polyominoes from its horizontal and vertical projections when the projections are defined as the number of cells of the polyomino in the different lines and columns was studied by Del Lungo and M. Nivat. In this paper, we study the reconstruction of any convex polyomino when the orthogonal projections are defined as the contour length of the object intercepted by the ray. We prove the NP-hardness of this problem for several classes of polyominoes: general, h-convex, v-convex. For hv-convex polyominoes we give a polynomial time algorithm for the reconstruction problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 346, Issues 2â3, 28 November 2005, Pages 439-454
Journal: Theoretical Computer Science - Volume 346, Issues 2â3, 28 November 2005, Pages 439-454
نویسندگان
C. Picouleau,