Adrian Dumitrescu
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