Algoritmické, strukturální a složitostní aspekty geometrických konfigurací
Cíle projektu
Konfigurace bodů, přímek, konvexních množin a dalších jednoduchých geometrických objektů v rovině a grafy zobrazené v rovině patří k základním strukturám při počítačové vizualizaci. Ve výzkumu budeme studovat některé důležité algoritmické, strukturální a složitostní otázky týkající se základních kombinatorických a konvexních vlastností rovinných nakreslení grafů, množin bodů, konvexních množin a dalších konfigurací v rovině. Budeme se zabývat zejména různými typy nakreslení grafu do roviny, průsečíková čísla, Erdősovu-Szekeresovu větu a extremální otázky pro vybrané typy geometrických konfigurací. Očekává se úplné nebo částečné řešení některých důležitých otevřených problémů.
Klíčová slova
discrete and computational geometrydiscrete mathematicstopologygraph drawingvisibility graphalgebraic methodspoint setsEuclidean spacegeometric graphtopological graphcrossing numbers
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
SGA0202100005
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
21-32817S
Alternativní jazyk
Název projektu anglicky
Algorithmic, structural and complexity aspects of geometric configurations
Anotace anglicky
Configurations of points, lines, convex sets and other simple geometric objects in the plane and graphs visualized in the plane belong to the basic structures of computer visualization. In our research we will study some important algorithmic, structural and complexity questions on basic combinatorial and convex properties of graph drawings in the plane, point sets and other configurations in the plane. We will deal mainly with various types of graph drawings in the plane, crossing numbers. Erdős-Szekeres theorem and extremal questions for selected types of geometric configurations. Full or partial solution of some important open problems is expected.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
OECD FORD - hlavní obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - vedlejší obor
—
OECD FORD - další vedlejší obor
—
CEP - odpovídající obory
(dle převodníku)AF - Dokumentace, knihovnictví, práce s informacemi
BC - Teorie a systémy řízení
BD - Teorie informace
IN - Informatika
Termíny řešení
Zahájení řešení
1. 1. 2021
Ukončení řešení
30. 6. 2024
Poslední stav řešení
—
Poslední uvolnění podpory
1. 4. 2024
Dodání dat do CEP
Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP25-GA0-GA-R
Datum dodání záznamu
12. 3. 2025
Finance
Celkové uznané náklady
4 397 tis. Kč
Výše podpory ze státního rozpočtu
3 920 tis. Kč
Ostatní veřejné zdroje financování
477 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
4 397 tis. Kč
Statní podpora
3 920 tis. Kč
89%
Poskytovatel
Grantová agentura České republiky
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Doba řešení
01. 01. 2021 - 30. 06. 2024