D 2017

On upward straight-line embeddings of oriented paths

CAGIRICI, Onur; Leonardo CASUSO; Medina CAROLINA; Miguel RAGGI; Edgardo ROLDAN-PENSADO et al.

Základní údaje

Originální název

On upward straight-line embeddings of oriented paths

Autoři

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

Vydání

EGC 2017, XVII Spanish Meeting on Computational Geometry, od s. 49-52, 4 s. 2017

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Španělsko

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

Klíčová slova česky

Výpočetní geometrie, pravděpodobnost, geometrické vkládání

Klíčová slova anglicky

Computational geometry, probability, geometric embedding

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 13. 6. 2022 16:10, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

GA17-00837S, projekt VaV
Název: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech
Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems