کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949122 1439983 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Drawing the Horton set in an integer grid of minimum size
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Drawing the Horton set in an integer grid of minimum size
چکیده انگلیسی
In 1978 Erdős asked if every sufficiently large set of points in general position in the plane contains the vertices of a convex k-gon, with the additional property that no other point of the set lies in its interior. Shortly after, Horton provided a construction-which is now called the Horton set-with no such 7-gon. In this paper we show that the Horton set of n points can be realized with integer coordinates of absolute value at most 12n12log⁡(n/2). We also show that any set of points with integer coordinates combinatorially equivalent (with the same order type) to the Horton set contains a point with a coordinate of absolute value at least c⋅n124log⁡(n/2), where c is a positive constant.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 63, June 2017, Pages 10-19
نویسندگان
, , , ,