## Abstract

We study some geometric maximization problems in the Euclidean plane under the non-crossing constraint. Given a set V of 2n points in general position in the plane, we investigate the following geometric configurations using straight-line segments and the Euclidean norm: (i) longest non-crossing matching, (ii) longest non-crossing hamiltonian path, (iii) longest non-crossing spanning tree. We propose simple and efficient algorithms to approximate these structures within a constant factor of optimality. Somewhat surprisingly, we also show that our bounds are within a constant factor of optimality even without the non-crossing constraint, For instance, we give an algorithm to compute a non-crossing matching whose total length is at least 2/π of the longest (possibly crossing) matching, and show that the ratio 2/π between the non-crossing and crossing matching is the best possible. Perhaps due to their utter simplicity, our methods also seem more general and amenable to applications in other similar contexts.

Original language | English (US) |
---|---|

Pages (from-to) | 385-394 |

Number of pages | 10 |

Journal | Fundamenta Informaticae |

Volume | 22 |

Issue number | 4 |

DOIs | |

State | Published - Jan 1 1995 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Algebra and Number Theory
- Information Systems
- Computational Theory and Mathematics