
Let \(R\) (red) and \(B\) (blue) be disjoint sets of points in the plane, each containing \(n\) points. An alternating cycle is a cycle graph drawn in the plane with vertex set \(R\cup B\) such that the endpoints of each edge have a different color. An alternating path may also be similarly defined. The length of a cycle or a path is the sum of its edge lengths. Only planar graphs are considered: edges are not allowed to cross. The authors present an algorithm for computing a planar alternating cycle of smallest possible length, in the case when the points of \(R\cup B\) are collinear, in \(\Theta(n\log{n})\) time. This algorithm is modified to compute a planar alternating path of minimal length in \(O(n^2)\) time, again assuming that points are collinear. For the case of 3 disjoint sets of points whose union is collinear, the authors give a \(O(n^2)\) time algorithm for computing a planar alternating cycle of minimum length. In contrast, for any number of disjoint sets that are not collinear, finding the shortest length planar alternating cycle is shown to be NP-hard.
alternating paths/cycles, algorithm, minimal length, Alternating paths/cycles; Colored points; Computer Science Applications1707 Computer Vision and Pattern Recognition; Geometry and Topology; Control and Optimization; Computational Theory and Mathematics; Computational Mathematics, planar graph, Planar graphs; geometric and topological aspects of graph theory, cycle graph, Numerical aspects of computer graphics, image analysis, and computational geometry, colored points, Computer graphics; computational geometry (digital and algorithmic aspects)
alternating paths/cycles, algorithm, minimal length, Alternating paths/cycles; Colored points; Computer Science Applications1707 Computer Vision and Pattern Recognition; Geometry and Topology; Control and Optimization; Computational Theory and Mathematics; Computational Mathematics, planar graph, Planar graphs; geometric and topological aspects of graph theory, cycle graph, Numerical aspects of computer graphics, image analysis, and computational geometry, colored points, Computer graphics; computational geometry (digital and algorithmic aspects)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
