| Autor: |
Mantas, Ioannis, Savić, Marko, Schrezenmaier, Hendrik |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Proc. 7th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM) 2021. Pages 151-164 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1007/978-3-030-67899-9_12 |
| Popis: |
Given a set of points in the plane, we are interested in matching them with straight line segments. We focus on perfect (all points are matched) non-crossing (no two edges intersect) matchings. Apart from the well known MinMax variation, where the length of the longest edge is minimized, we extend work by looking into different optimization variants such as MaxMin, MinMin, and MaxMax. We consider both the monochromatic and bichromatic versions of these problems and by employing diverse techniques we provide efficient algorithms for various input point configurations. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
