Akademska digitalna zbirka SLovenije - logo
ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Maximizing the area of overlap of two unions of disks under rigid motion
    Berg, Mark de ...
    Let ▫$A$▫ and ▫$B$▫ be two sets of ▫$n$▫ resp. ▫$m$▫ disjoint unit disks in the plane, with ▫$m \ge n$▫. We consider the problem of finding a translation or rigid motion of ▫$A$▫ that maximizes the ... total area of overlap with ▫$B$▫. The function describing the area of overlap is quite complex, even for combinatorially equivalent translations and, hence, we turn our attention to approximation algorithms. We give deterministic ▫$(1-\epsilon)$▫-approximation algorithms for translations and for rigid motions, which run in ▫$O((nm/\epsilon^2) \log (m/\epsilon))$▫ and ▫$O((n^2m^2/\epsilon^3)\log m)$▫ time, respectively. For rigid motions, we can also compute a ▫$(1-\epsilon)$▫-approximation in ▫$O((m^2n^{4/3}\Delta^{1/3}/\epsilon^3) \log n \log m)$▫ time, where ▫$\Delta$▫ is the diameter of set ▫$A$▫. Under the condition that the maximum area of overlap is at least a constant fraction of the area of ▫$A$▫, we give a probabilistic ▫$(1-\epsilon)$▫-approximation algorithm for rigid motions that runs in ▫$O((m^2/\epsilon^4) \log^2 (m/\epsilon)\log m)$▫ time. Our results generalize to the case where ▫$A$▫ and ▫$B$▫ consist of possibly intersecting disks of different radii, provided that (i) the ratio of the radii of any two disks in ▫$A\cup B$▫ is bounded, and (ii) within each set, the maximum number of disks with a non-empty intersection is bounded.
    Source: International journal of Computational geometry and applications. - ISSN 0218-1959 (Vol. 19, iss. 6, 2009, str. 533-556)
    Type of material - article, component part
    Publish date - 2009
    Language - english
    COBISS.SI-ID - 15575641

    Link(s):

    http://dx.doi.org/10.1142/S0218195909003118

Shelf entry