# Long non-crossing configurations in the plane

We revisit some maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1993). Given a set of n points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching (b) a Hamiltonian path (c) a spanning tree. Here we obtain some new results for (b) and (c), as well as for the Hamiltonian cycle problem:
(i) For the longest non-crossing Hamiltonian path problem, we give an approximation algorithm with ratio 2/pi+1. The previous best ratio, due to Alon et al., was 1^pi. The ratio of our algorithm is close to 2^pi on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. For instance "random" point sets meet the condition with high probability. The algorithm runs in O(n^{7/3} log n) time.
(ii) For the longest non-crossing spanning tree problem, we give an approximation algorithm with ratio 0.502 which runs in O(n log n) time. The previous ratio, 1/2, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first re-derive the result of Alon et al. with a faster algorithm and a very simple analysis.
(iii) For the longest non-crossing Hamiltonian cycle problem, we give an approximation algorithm whose ratio is close to 2^pi on a relatively broad class of instances: for point sets with the product much smaller than the maximum length matching. Again "random" point sets meet the condition with high probability. The algorithm runs in O(n^{7/3} log n) time. No previous approximation results were known for this problem.