Med tanke på en uppsättning S av n punkter i k-dimensionellt utrymme, och en L t-mått, är det dynamiska närmaste par problemet de ned på följande sätt: nd ett närmaste par S efter varje uppdatering av S (infogningen eller strykningen av en punkt). För xed dimension k och xed metrisk L t, ger vi en datastruktur av storlek O(n) som upprätthåller ett närmast par S i O(log n) tid per insättning och radering. Driftstiden för algoritmen är optimal upp till konstant faktor eftersom (log n) är en lägre gräns, i algebraiska beslutsträd modell av beräkning, på tiden komplexitet av någon algoritm som upprätthåller det närmaste paret (för k = 1). Algoritmen är baserad på det rättvisesplitta trädet. Den konstanta faktorn i uppdateringstiden är exponentiell i dimensionen. Vi modifierar det rättvisa trädet för att minska det.
I REF beskrivs en optimal algoritm för att upprätthålla de närmaste punkterna.
An Optimal Algorithm for Closest Pair Maintenance
{'venue': 'Discrete Comput. Geom', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}