## Hamiltonian Alternating Paths on Bicolored Double-Chains
Cibulka, Josef and Kynčl, Jan and Meszaros, Viola and Stolar, Rudolf and Valtr, Pavel
(2009)
Full text not available from this repository. ## AbstractWe ﬁnd arbitrarily large ﬁnite sets S of points in general position in the plane with the following property. If the points of S are equitably 2-colored (i.e., the sizes of the two color classes differ by at most one), then there is a polygonal line consisting of straight-line segments with endpoints in S , which is Hamiltonian, non-crossing, and alternating (i.e., each point of S is visited exactly once, every two non-consecutive segments are disjoint, and every segment connects points of different colors). We show that the above property holds for so-called double-chains with each of the two chains containing at least one ﬁfth of all the points. Our proof is constructive and can be turned into a linear-time algorithm. On the other hand, we show that the above property does not hold for double-chains in which one of the chains contains at most ≈ 1/29 of all the points.
Repository Staff Only: item control page References |