Il me semble qu'il manque des hypothèses à ton énoncé.
1) Les points ne doivent pas être alignés (OK c'est trivial, mais ça va mieux en le disant)
2) Si P1, P3, P5, .. P2k+1 sont alignés, alors la droite qui passent par ces points à un point commun avec chaque segment. Ce qui contredit ton énoncé.
P1, P2, .. P2k+1 doivent-ils dessiner une figure convexe ? ça me semble trop facile dans ce cas.
Est-ce que la contrainte supplémentaire est que

ne doit contenir aucun des Pi ? (la droite passerait "strictement à l'intérieur" des segments)
Merci par avance de tes précisions