TY - JOUR

T1 - Maximizing the area of overlap of two unions of disks under rigid motion

AU - Berg, de, M.

AU - Cabello, S.

AU - Giannopoulos, P.

AU - Knauer, C.

AU - Oostrum, van, R.

AU - Veltkamp, R.C.

PY - 2009

Y1 - 2009

N2 - Let A and B be two sets of n resp. m disjoint unit disks in the plane, with m > 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 - ¿)- approximation algorithms for translations and for rigid motions, which run in O((nm/¿2) log(m/¿)) and O((n2m2/¿3) log m)) time, respectively. For rigid motions, we can also compute a (1 - ¿)-approximation in O((m2 n4/3¿1/3/¿3) log n log m) time, where ¿ 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 - ¿)-approximation algorithm for rigid motions that runs in O((m2/¿4) log(m/¿) log2 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 U B is bounded, and (ii) within each set, the maximum number of disks with a non-empty intersection is bounded.

AB - Let A and B be two sets of n resp. m disjoint unit disks in the plane, with m > 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 - ¿)- approximation algorithms for translations and for rigid motions, which run in O((nm/¿2) log(m/¿)) and O((n2m2/¿3) log m)) time, respectively. For rigid motions, we can also compute a (1 - ¿)-approximation in O((m2 n4/3¿1/3/¿3) log n log m) time, where ¿ 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 - ¿)-approximation algorithm for rigid motions that runs in O((m2/¿4) log(m/¿) log2 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 U B is bounded, and (ii) within each set, the maximum number of disks with a non-empty intersection is bounded.

U2 - 10.1142/S0218195909003118

DO - 10.1142/S0218195909003118

M3 - Article

VL - 19

SP - 533

EP - 556

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

SN - 0218-1959

IS - 6

ER -