A note on two geometric paths with few crossings for points labeled by integers in the plane

摘要

Let S be a set of n points in the plane in general position such that the integers 1, 2, ..., n are assigned to the points bijectively. Set h be an integer with 1 = h n(n + 1)/2. In this paper we consider the problem of finding two vertex-disjoint simple geometric paths consisting of all points of S such that the sum of labels of the points in one path is equal to h and the paths have as few crossings as possible. We prove that there exists such a pair of paths with at most two crossings between them. (C) 2017 Elsevier B.V. All rights reserved.