On upward straight-line embeddings of oriented paths
| Autoři | |
|---|---|
| Rok publikování | 2017 |
| Druh | Článek ve sborníku |
| Konference | EGC 2017, XVII Spanish Meeting on Computational Geometry |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | The book of abstracts where the publication is available online |
| Klíčová slova | Computational geometry, probability, geometric embedding |
| Popis | We investigate upward straight-line embeddings (UPSEs) 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. |
| Související projekty: |