|
|||||
|
|
On the length of longest alternating paths for multicoloured point sets in convex position |
|
| Authors: | C Merino G Salazar J Urrutia |
| Institution: | a Instituto de Matemáticas, U.N.A.M., Área de la Investigación Científica, Circuito Exterior, Ciudad Universitaria, Coyoacán 04510, México D.F., México b Instituto de Física, Universidad Autónoma de San Luis Potosí, Alvaro Obregón 64, San Luis Potosí, SLP 78000, México |
| 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. |
| Keywords: | Alternating path Multicoloured point set Finite point set in convex position |
| 本文献已被 ScienceDirect 等数据库收录！ | |