Publication at Faculty of Mathematics and Physics |
2008
Abstract
Given n red and n blue points in convex position in the plane, we show that there exists a noncrossing alternating path of length n + c(n/log n)^{1/2}. We disprove a conjecture of Erdős by constructing an example without any such path of length greater than 4n/3 + c'n^{1/2}.