Alternující cesty v obarvených bodových množinách v konvexní poloze

Abstract

This thesis deals with the problem of the longest alternating paths in colored point sets in a convex position, especially in point sets with n red and n blue points. The aim of the thesis is to summarize the main results in this area and put them in context. First, we present the basic concepts and the algorithm for finding the longest alternating path on a specific point set. We express l(n), the largest number such that for each arrangement of 2n points with n red and n blue points, there is an alternating path of at least l(n). We show the connection of l(n) to the problem of the largest separated matching. We present the most important lower and upper bounds of l(n), including the best ones published so far. Finally, we generalize the problem for multicolored point sets and show the related problem about (anti)palindromic subsequences of binary circular words.

Tato práce se zabývá problémem nejdelších alternujících cest v obarve- ných bodových množinách v konvexní poloze, především v bodových množi- nách s n červenými a n modrými body. Cílem práce je shrnout hlavní výsledky dosažené v této oblasti a dát je do souvislostí. Nejprve uvedeme základní po- jmy a algoritmus pro hledání nejdelší alternující cesty na konkrétní bodové množině. Vyjádříme si l(n), největší číslo takové, že pro každé uspořádání 2n bodů s n červenými a n modrými body existuje alternující cesta o délce alespoň l(n). Ukážeme souvislost l(n) s problémem největšího separovaného párování. Uvedeme nejdůležitější dolní i horní odhady l(n), včetně nejlepších dosud publikovaných. Nakonec zobecníme problém pro více barev a ukážeme související problém o (anti)palindromech binárních cyklických slov.