On the length of longest alternating paths for multicoloured point sets in convex position
Article
Overview
Research
Identity
Additional Document Info
View All
Overview
abstract
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.
publication date
published in
Research
keywords
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
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue