On upward straight-line embeddings of oriented paths

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

CAGIRICI Onur CASUSO Leonardo CAROLINA Medina RAGGI Miguel ROLDAN-PENSADO Edgardo SALAZAR Gelasio URRUTIA Jorge

Rok publikování 2017
Druh Článek ve sborníku
Konference EGC 2017, XVII Spanish Meeting on Computational Geometry
Fakulta / Pracoviště MU

Fakulta informatiky

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.