[PDF][PDF] On upward straight-line embeddings of oriented paths
O Cagırıcı, L Casuso, C Medina, T Patino… - XVII Spanish Meeting …, 2017 - cagirici.net
XVII Spanish Meeting on Computational Geometry, 2017•cagirici.net
We investigate upward straight-line embeddings (UP-SEs) of oriented paths. Along the lines
of similar results in the literature, we find a condition—related to the number of vertices in
between sources and sinks of an oriented path—that guarantees that an oriented path
satisfying the condition on n vertices admits an UPSE into any n-point set in general
position. We also show that the following holds for every ε> 0. If S is a set of n points chosen
uniformly at random in the unit square, and P is an oriented path on at most (1/3− ε) n …
of similar results in the literature, we find a condition—related to the number of vertices in
between sources and sinks of an oriented path—that guarantees that an oriented path
satisfying the condition on n vertices admits an UPSE into any n-point set in general
position. We also show that the following holds for every ε> 0. If S is a set of n points chosen
uniformly at random in the unit square, and P is an oriented path on at most (1/3− ε) n …
Abstract
We investigate upward straight-line embeddings (UP-SEs) of oriented paths. Along the lines of similar results in the literature, we find a condition—related to the number of vertices in between sources and sinks of an oriented path—that guarantees that an oriented path satisfying the condition on n vertices admits an UPSE into any n-point set in general position. We also show that the following holds for every ε> 0. If S is a set of n points chosen uniformly at random in the unit square, and P is an oriented path on at most (1/3− ε) n vertices, then with high probability P has an UPSE into S.
cagirici.net
以上显示的是最相近的搜索结果。 查看全部搜索结果