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

Let P be a set of points in R2 in general position such that each point is coloured with one of k colours. An alternating path of P is a simple polygonal whose edges are straight line segments joining pairs of elements of P with different colours. In this paper we prove the following: suppose that each colour class has cardinality s and P is the set of vertices of a convex polygon. Then P always has an alternating path with at least (k - 1) s elements. Our bound is asymptotically sharp for odd values of k. © 2006 Elsevier B.V. All rights reserved.

Alternating path; Finite point set in convex position; Multicoloured point set Computation theory; Computational methods; Finite difference method; Set theory; Alternating path; Finite point set in convex position; Multicoloured point set; Numerical methods

VIVO