Vi anser att det är ett problem med intervalltäckning. Med tanke på n-intervall av samma längd på en linje L och ett linjesegment B på L, vill vi flytta intervallen längs L så att varje punkt av B täcks av minst ett intervall och summan av de rörliga avstånden av alla intervall minimeras. Som ett grundläggande geometriproblem har den applikationer inom mobil sensorbarriärtäckning i trådlösa sensornätverk. Det tidigare arbetet löste problemet i O(n 2 ) tid. I detta dokument, genom att upptäcka många intressanta observationer och utveckla nya algoritmiska tekniker, presenterar vi en O (n log n) tid algoritm. Vi visar även en lägre tid (n log n) för detta problem, vilket innebär att vår algoritm är optimal.
På liknande sätt, i ett homogent trådlöst sensornätverk, Wang et al. REF presenterar en O(n log n) algoritm för att minimera sensorernas totala rörelse på ett linjeintervall.
Minimizing the Aggregate Movements for Interval Coverage
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}