کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414702 681009 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximizing maximal angles for plane straight-line graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Maximizing maximal angles for plane straight-line graphs
چکیده انگلیسی

Let G=(S,E)G=(S,E) be a plane straight-line graph on a finite point set S⊂R2S⊂R2 in general position. The incident angles   of a point p∈Sp∈S in G are the angles between any two edges of G that appear consecutively in the circular order of the edges incident to p. A plane straight-line graph is called φ-open if each vertex has an incident angle of size at least φ. In this paper we study the following type of question: What is the maximum angle φ   such that for any finite set S⊂R2S⊂R2 of points in general position we can find a graph from a certain class of graphs on S that is φ-open? In particular, we consider the classes of triangulations, spanning trees, and spanning paths on S and give tight bounds in most cases.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 1, January 2013, Pages 17–28
نویسندگان
, , , , , , , ,