  The enabling of safe cellular controlled unmanned aerial vehicle (UAV) beyond
visual line of sight is expected to open important future opportunities in the
area of transportation, goods delivery, and system monitoring. A key challenge
in this area lies in the design of trajectories which, while allowing the
completion of the UAV mission, can guarantee reliable cellular connectivity all
along the path. Previous approaches in this domain have considered simplistic
propagation model assumptions (e.g. Line of Sight based) or more advanced
models but with computationally demanding optimized solutions. In this paper,
we propose a novel approach for trajectory design using a coverage map that can
be obtained with a combination of 3D map of the environment and radio
propagation models. Leveraging on the convexity of sub-regions within the
coverage map, we propose a low-complexity graph based algorithm which is shown
to achieve quasi-optimal performance at a fraction of the computational cost of
known optimal methods.
