Ett flaskhalsplan perfekt matchning av en uppsättning n punkter i R 2 definieras som en perfekt icke-korsande matchning som minimerar längden på den längsta kanten; längden på denna längsta kant kallas flaskhals. Problemet med att beräkna en flaskhals plan perfekt matchning har visat sig vara NP-hård. Vi presenterar en algoritm som beräknar ett flaskhalsplan som matchar storlek minst n 5 i O(n log 2 n)-tid. Sedan utökar vi vår idé mot en O(n log n)-tids approximationsalgoritm som beräknar ett plan som matchar storlek minst 2n 5 vars kanter har längd högst 2 + 3 gånger flaskhalsen.
I REF, Abu-Affash, Biniaz, Carmi, Maheshwari och Smid presenterade en algoritm för att beräkna en icke-crossing flaskhals plan matchning av storlek minst n/5 i O(n log 2 n) tid.
Approximating the Bottleneck Plane Perfect Matching of a Point Set
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}