کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414323 680888 2012 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An improved algorithm for reconstructing a simple polygon from its visibility angles
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
An improved algorithm for reconstructing a simple polygon from its visibility angles
چکیده انگلیسی

Given a cyclically ordered vertex sequence of an unknown simple polygon P of n vertices and, for each vertex v of P, the sequence of angles defined by all the visible vertices of v in P, we study the problem of reconstructing the polygon P   (up to similarity). An O(n3logn) time algorithm has been proposed for this problem (by Disser, Mihalák, and Widmayer in 2011 [5]). We show in this paper that the running time of the algorithm in the previous work can be reduced to O(n2)O(n2) time by new observations on the geometric structures of the problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 45, Issues 5–6, July 2012, Pages 254–257
نویسندگان
, ,