I detta dokument studerar vi problemet med att flytta n-sensorer på en linje för att bilda en barriärtäckning av ett specificerat segment av linjen så att det maximala rörelseavståndet för sensorerna minimeras. Tidigare var det en öppen fråga om detta problem på sensorer med godtyckliga avkänningsintervall kan lösas i polynom tid. Vi löser denna öppna fråga positivt genom att ge en O(n 2 log n) tid algoritm. För specialfallet när alla sensorer har samma storlek avkänningsområde tar den tidigare bästa lösningen O(n 2 ) tid. Vi presenterar en O(n log n) tid algoritm för detta fall; vidare, om alla sensorer är initialt placerade på täckning segment, vår algoritm tar O(n) tid. Dessutom utökar vi våra tekniker till cykelversionen av problemet där barriärtäckningen är för en enkel cykel och sensorerna tillåts bara röra sig längs cykeln. För sensorer med samma storlekssensorer löser vi cykelversionen i O(n) tid, vilket förbättrar den tidigare bästa O(n 2 ) tidslösningen. - Vad är det för fel på dig?
Om intervallen har olika längder, Chen et al. REF löste problemet under O(n 2 log n) tid.
Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain
{'venue': 'Discrete&Computational Geometry, Vol. 50(2), pages 374-408, 2013', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}