کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6868398 1439973 2018 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Holes in 2-convex point sets
ترجمه فارسی عنوان
سوراخ در مجموعه ای از دو نقطه محدب
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Considering a typical Erdős-Szekeres-type problem, we show that every 2-convex point set of size n contains an Ω(log⁡n)-hole. In comparison, it is well known that there exist arbitrarily large point sets in general position with no 7-hole. Further, we show that our bound is tight by constructing 2-convex point sets in which every hole has size O(log⁡n).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 74, October 2018, Pages 38-49
نویسندگان
, , , , , , ,