Minimum width color spanning annulus

0534825 - ÚI 2021 NL eng J - Článek v odborném periodiku
Acharyya, Ankush - Nandy, S. C. - Roy, S.
Minimum width color spanning annulus.
Theoretical Computer Science. Roč. 725 (2018), s. 16-30. ISSN 0304-3975. E-ISSN 1879-2294
Klíčová slova: Location planning * Color spanning annulus * Algorithms * Complexity
Impakt faktor: 0.718, rok: 2018

Given a set P = {P-1, P-2, . . . , P-n} of n points in R-2 and each assigned with one of the given k distinct colors, we study the problem of finding the minimum width color spanning annulus of different shapes. Specifically, we consider the color spanning circular annulus (CSCA), axis-parallel square annulus (CSSA), axis parallel rectangular annulus (CSRA), and equilateral triangular annulus of fixed orientation (CSETA). The time complexities of the proposed algorithms for the respective problems are (i) O(n(3) logn) for CSCA, (ii) O(n(3) + n(2)k logk) for CSSA, (iii) O(n(4)) for CSRA, and (iv) O(n(2)k) for CSETA.
Trvalý link: http://hdl.handle.net/11104/0312986