Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414702 | Computational Geometry | 2013 | 12 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Clemens Huemer, Attila Pór, Francisco Santos, Bettina Speckmann, Birgit Vogtenhuber,