کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
415654 681222 2013 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Ice-creams and wedge graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Ice-creams and wedge graphs
چکیده انگلیسی

What is the minimum angle α>0α>0 such that given any set of α-directional antennas (that is, antennas each of which can communicate along a wedge of angle α), one can always assign a direction to each antenna such that the resulting communication graph is connected? Here two antennas are connected by an edge if and only if each lies in the wedge assigned to the other. This problem was recently presented by Carmi, Katz, Lotker, and Rosén (2011) [2] who also found the minimum such α   namely α=π3. In this paper we give a simple proof of this result. Moreover, in our construction each antenna can be assigned one of two possible directions and the diameter of the resulting communication graph is at most four.Our main tool is a surprisingly basic geometric lemma that is of independent interest. We show that for every compact convex set S   in the plane and every 0<α<π0<α<π, there exist a point O and two supporting lines to S passing through O and touching S at two single points X and Y  , respectively, such that |OX|=|OY||OX|=|OY| and the angle between the two lines is α.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 3, April 2013, Pages 213–218
نویسندگان
, , ,