کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429704 687638 2008 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The orchard visibility problem and some variants
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The orchard visibility problem and some variants
چکیده انگلیسی

Imagine that you are standing at the center of a circular orchard, with trees centered at all of the lattice points except there is no tree at the origin itself (where you are standing). How large must the radius of the trees be in order to completely block your view (in every direction). Let R be the radius of the orchard, and r be the radius of the trees. It turns out that if R (the radius of the orchard) is an integer then you can see out if and only if . Allen [T.T. Allen, Polya's orchard problem, Amer. Math. Monthly 93 (1986) 98–104] attributes this problem to Polya [G. Polya, Zahlentheoretisches und wahrscheinlichkeitstheoretisches über die Sichtweite im Walde, Arch. Math. Phys. Ser. 2 27 (1918) 135–142] and solves it using trigonometric techniques. He generalizes the result to orchards whose radius is not an integer. We give an alternative proof of these results based on the Stern–Brocot wreath. We generalize the results to parallelogram lattices. We also consider the problem of what radius the trees need to have to block the view between some pair of trees. For parallelogram lattices, the ratio between the radius needed to block the view between all trees and the radius needed to block the view between some pair of trees asymptotically approaches 2 (as the radius of the orchard increases).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 74, Issue 4, June 2008, Pages 587-597