×

zbMATH — the first resource for mathematics

Simple alternating path problem. (English) Zbl 0699.05032
Summary: Let A be a set of 2n points in general position on a plane, and suppose n of the points are coloured red while the remaining are coloured blue. An alternating path P of A is a sequence \(p_ 1,p_ 2,...,p_{2n}\) of points of A such that \(p_{2i}\) is blue and \(p_{2i+1}\) is red. P is simple if it does not intersect itself. We determine the condition under which there exists a simple alternating path P of A for the case when the 2n points are the vertices of a convex polygon. As a consequence an \(O(n^ 2)\) algorithm to find such an alternating path (if it exists) is obtained.

MSC:
05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
52Bxx Polytopes and polyhedra
PDF BibTeX Cite
Full Text: DOI
References:
[1] Akiyama, J.; Alon, N., Disjoint simplices and geometric hypergraphs, Ann. New York acad. sci., 555, 1-3, (1989) · Zbl 0734.05064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.