VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Covering point sets with two disjoint disks or squares
    Cabello, Sergio ...
    We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks ▫$C_R$▫ and ▫$C_B$▫ with disjoint interiors such that the number of red points ... covered by ▫$C_R$▫ plus the number of blue points covered by ▫$C_B$▫ is maximized. We give an algorithm to solve this problem in ▫$O(n^{8/3}\log^2 n)$▫ time, where ▫$n$▫ denotes the total number of points. We also show that the analogous problem of finding two axis-aligned unit squares ▫$S_R$▫ and ▫$S_B$▫ instead of unit disks can be solved in ▫$O(n\log n)$▫ time, which is optimal. If we do not restrict ourselves to axis-aligned squares, but require that both squares have a common orientation, we give a solution using ▫$O(n^3\log n)$▫ time.
    Vir: Computational geometry. - ISSN 0925-7721 (Vol. 40, iss. 3, 2008, str. 195-206)
    Vrsta gradiva - članek, sestavni del
    Leto - 2008
    Jezik - angleški
    COBISS.SI-ID - 14646873

    Povezava(-e):

    http://dx.doi.org/10.1016/j.comgeo.2007.10.001

vir: Computational geometry. - ISSN 0925-7721 (Vol. 40, iss. 3, 2008, str. 195-206)
loading ...
loading ...
loading ...

Vnos na polico