On the length of longest alternating paths for multicoloured point sets in convex position

Abstract: Let be a set of points in in general position such that each point is coloured with one of colours. An alternating path of is a simple polygonal whose edges are straight line segments joining pairs of elements of with different colours. In this paper we prove the following: suppose that each colour class has cardinality and is the set of vertices of a convex polygon. Then always has an alternating path with at least elements. Our bound is asymptotically sharp for odd values of . [Copyright &y& Elsevier]