کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868398 | 1439973 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Holes in 2-convex point sets
ترجمه فارسی عنوان
سوراخ در مجموعه ای از دو نقطه محدب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Computational Geometry - Volume 74, October 2018, Pages 38-49
نویسندگان
Oswin Aichholzer, Martin Balko, Thomas Hackl, Alexander Pilz, Pedro Ramos, Pavel Valtr, Birgit Vogtenhuber,