Abstract
Let G = (S, E) be a plane straight-line graph on a finite point set in general position. The incident angles of a point p ∈ 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
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 paths on S and give tight bounds in most cases.
O.A., T.H., and B.V. were supported by the Austrian FWF Joint Research Project ’Industrial Geometry’ S9205-N12. C.H. was partially supported by projects MEC MTM2006-01267 and Gen. Cat. 2005SGR00692. A.P. was partially supported by Hungarian National Foundation Grant T60427. F.S. was partially supported by grant MTM2005-08618-C02-02 of the Spanish Ministry of Education and Science. Preliminary results of this article have been presented in [1].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aichholzer, O., Hackl, T., Hoffmann, M., Huemer, C., Santos, F., Speckmann, B., Vogtenhuber, B.: Maximizing Maximal Angles for Plane Straight Line Graphs - Extended Abstract. In: Abstracts 23rd European Workshop Comput. Geom., pp. 98–101 (2007)
Aurenhammer, F., Xu, Y.-F.: Optimal Triangulations. Encyclopedia of Optimization 4, 160–166 (2000)
Aichholzer, O., Aurenhammer, F., Krasser, H., Brass, P.: Pseudo-Triangulations from Surfaces and a Novel Type of Edge Flip. SIAM J. Comput. 32(6), 1621–1653 (2003)
Aggarwal, A., Coppersmith, D., Khanna, S., Motwani, R., Schieber, B.: The Angular-Metric Traveling Salesman Problem. SIAM J. Comput. 29(3), 697–711 (1999)
Arkin, E., Fekete, S., Hurtado, F., Mitchell, J., Noy, M., Sacristán, V., Sethia, S.: On the Reflexivity of Point Sets. In: Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Springer, Heidelberg (2003)
Bárány, I., Pór, A., Valtr, P.: Paths with no Small Angles. Manuscript in preparation (2006)
Bern, M., Eppstein, D., Gilbert, J.: Provably Good Mesh Generation. J. Comput. Syst. Sci. 48(3), 384–409 (1994)
Dai, Y., Katoh, N., Cheng, S.-W.: LMT-Skeleton Heuristics for Several New Classes of Optimal Triangulations. Comput. Geom. Theory Appl. 17(1-2), 51–68 (2000)
Eppstein, D.: The Farthest Point Delaunay Triangulation Minimizes Angles. Comput. Geom. Theory Appl. 1(3), 143–148 (1992)
Edelsbrunner, H., Tan, T.S., Waupotitsch, R.: An O(n 2 logn) Time Algorithm for the Minmax Angle Triangulation. SIAM J. Sci. Stat. Comput. 13(4), 994–1008 (1992)
Fekete, S.P., Woeginger, G.J.: Angle-Restricted Tours in the Plane. Comput. Geom. Theory Appl. 8(4), 195–218 (1997)
Haas, R., Orden, D., Rote, G., Santos, F., Servatius, B., Servatius, H., Souvaine, D., Streinu, I., Whiteley, W.: Planar Minimally Rigid Graphs and Pseudo-Triangulations. Comput. Geom. Theory Appl. 31(1-2), 31–61 (2005)
Kirkpatrick, D., Snoeyink, J., Speckmann, B.: Kinetic Collision Detection for Simple Polygons. Internat. J. Comput. Geom. Appl. 12(1-2), 3–27 (2002)
Keil, J.M., Vassilev, T.S.: The Relative Neighbourhood Graph is a Part of Every 30deg-Triangulation. Abstracts 21st European Workshop Comput. Geom., pp. 9–12 (2005)
Rote, G., Santos, F., Streinu, I.: Pseudo-Triangulations – a Survey. Manuscript (2006), http://arxiv.org/abs/math/0612672
Streinu, I.: Pseudo-Triangulations, Rigidity and Motion Planning. Discrete Comput. Geom. 34(4), 587–635 (2005)
Vogtenhuber, B.: On Plane Straight Line Graphs. Master’s Thesis, Graz University of Technology, Graz, Austria (January 2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aichholzer, O. et al. (2007). Maximizing Maximal Angles for Plane Straight-Line Graphs. In: Dehne, F., Sack, JR., Zeh, N. (eds) Algorithms and Data Structures. WADS 2007. Lecture Notes in Computer Science, vol 4619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73951-7_40
Download citation
DOI: https://doi.org/10.1007/978-3-540-73951-7_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73948-7
Online ISBN: 978-3-540-73951-7
eBook Packages: Computer ScienceComputer Science (R0)