کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868491 | 1439978 | 2018 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Strong matching of points with geometric shapes
ترجمه فارسی عنوان
تطبیق قوی از نقاط با اشکال هندسی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
حداکثر تطبیق تطبیق قوی، نمودار هندسی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let P be a set of n points in general position in the plane. Given a convex geometric shape S, a geometric graph GS(P) on P is defined to have an edge between two points if and only if there exists a homothet of S having the two points on its boundary and whose interior is empty of points of P. A matching in GS(P) is said to be strong, if the homothets of S representing the edges of the matching are pairwise disjoint, i.e., they do not share any point in the plane. We consider the problem of computing a strong matching in GS(P), where S is a diametral disk, an equilateral triangle, or a square. We present an algorithm that computes a strong matching in GS(P); if S is a diametral-disk, then it computes a strong matching of size at least ânâ117â, and if S is an equilateral-triangle, then it computes a strong matching of size at least ânâ19â. If S can be a downward or an upward equilateral-triangle, we compute a strong matching of size at least ânâ14â in GS(P). When S is an axis-aligned square, we compute a strong matching of size at least ânâ14â in GS(P), that improves the previous lower bound of ân5â.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 68, March 2018, Pages 186-205
Journal: Computational Geometry - Volume 68, March 2018, Pages 186-205
نویسندگان
Ahmad Biniaz, Anil Maheshwari, Michiel Smid,