### 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) |
---|---|

Title of host publication | Proceedings of the 9th Annual Symposium on Computational Geometry |

Publisher | Publ by ACM |

Pages | 257-263 |

Number of pages | 7 |

ISBN (Print) | 0897915828, 9780897915823 |

DOIs | |

State | Published - 1993 |

Externally published | Yes |

Event | Proceedings of the 9th Annual Symposium on Computational Geometry - San Diego, CA, USA Duration: May 19 1993 → May 21 1993 |

### Publication series

Name | Proceedings of the 9th Annual Symposium on Computational Geometry |
---|

### Other

Other | Proceedings of the 9th Annual Symposium on Computational Geometry |
---|---|

City | San Diego, CA, USA |

Period | 5/19/93 → 5/21/93 |

### All Science Journal Classification (ASJC) codes

- Engineering(all)

## Fingerprint Dive into the research topics of 'Long non-crossing configurations in the plane'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 9th Annual Symposium on Computational Geometry*(pp. 257-263). (Proceedings of the 9th Annual Symposium on Computational Geometry). Publ by ACM. https://doi.org/10.1145/160985.161145