Barrier Coverage Problem in 2D

Adil Erzin, Natalya Lagutkina

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

3 Цитирования (Scopus)

Аннотация

This paper deals with the NP-hard problem of covering a line segment by n initially arbitrarily arranged circles on the plane by moving their centers to the segment in such a way that the sum of the Euclidean distances between the initial and final positions of the centers of the disks would be minimal. In the case of identical circles, a dynamic programming algorithm is known, which constructs a –approximate solution to the problem with O(n 4 ) –time complexity. In this paper, we propose a new algorithm that has the same accuracy, but the complexity of which is reduced by n 2 times to O(nn 2 ).

Язык оригиналаанглийский
Название основной публикацииAlgorithms for Sensor Systems - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018, Revised Selected Papers
РедакторыDanny Hughes, Seth Gilbert, Bhaskar Krishnamachari
ИздательSpringer-Verlag GmbH and Co. KG
Страницы118-130
Число страниц13
ISBN (печатное издание)9783030140939
DOI
СостояниеОпубликовано - 1 янв 2019
Событие14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018 - Helsinki, Финляндия
Продолжительность: 23 авг 201824 авг 2018

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11410 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018
СтранаФинляндия
ГородHelsinki
Период23.08.201824.08.2018

Fingerprint Подробные сведения о темах исследования «Barrier Coverage Problem in 2D». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Erzin, A., & Lagutkina, N. (2019). Barrier Coverage Problem in 2D. В D. Hughes, S. Gilbert, & B. Krishnamachari (Ред.), Algorithms for Sensor Systems - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018, Revised Selected Papers (стр. 118-130). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11410 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-14094-6_8