Back to Search Start Over

On the plane angle-monotone graphs

Authors :
Mohammad Farshi
Davood Bakhshesh
Source :
Computational Geometry. 100:101818
Publication Year :
2022
Publisher :
Elsevier BV, 2022.

Abstract

Let P = ( p 1 , … , p n ) be a geometric path in the plane. For a real number 0 γ 180 ° , P is called an angle-monotone path with width γ if there exists a closed wedge of angle γ such that the vector of every edge ( p i , p i + 1 ) of P lies in this wedge. Let G be a geometric graph in the plane. The graph G is called angle-monotone with width γ if there exists an angle-monotone path with width γ between any two vertices. Let γ min be the smallest width such that every set of points in the plane has a plane angle-monotone graph with width γ min . It has been shown that 90 ° γ min ≤ 120 ° . In this paper, we show that γ min = 120 ° . This solves an open problem posed by Bonichon et al. [GD 2016].

Details

ISSN :
09257721
Volume :
100
Database :
OpenAIRE
Journal :
Computational Geometry
Accession number :
edsair.doi...........c3ec85a716743780a52a28db3a4430c7
Full Text :
https://doi.org/10.1016/j.comgeo.2021.101818