Long Non-crossing Configurations in the Plane

Adrian Dumitrescu & Csaba D. Tóth
We revisit several 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 new results for (b) and (c), as...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our Documentation.