Repositorio de producción científica de la Universidad de Sevilla

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

 

Advanced Search
 
Opened Access Maximizing the area of overlap of two unions of disks under rigid motion
Cites
Show item statistics
Icon
Export to
Author: Berg, Mark de
Cabello Justo, Sergio
Giannopoulos, Panos
Knauer, Christian
Van Oostrum, René
Veltkamp, Remco C.
Date: 2004
Document type: Presentation
Abstract: Let A and B be two sets of n resp. m (m ≥ n) disjoint unit disks in the plane. We consider the problem of finding a rigid motion of A that maximizes the total area of its overlap with B. The function describing the area of overlap is quite complex, even for combinatorially equivalent translations, and hen e, we turn our attention to approximation algorithms. We give deterministic (1-€)-approximation algorithms for the maximum area of overlap under translation and rigid motion that run in O((nm= 2) log(m= )) and O((n2m2 = 3) log m)) time respectively. For the later, if is the diameter of set A, we get an (1-€)-approximation in O(m2 n4=3 1=3 log n log m3) time which is improvement when = o(n2). Under the condition that the maximum is at least a constant fraction of the area of B, we give a probabilistic (1-€)-approximation algorithm for rigid motions that runs in O((n2 = 5) log2(n= )) time and suceeds with probability at least 1 -e -c n -6.
Cite: Berg, M.d., Cabello Justo, S., Giannopoulos, P., Knauer, C., Van Oostrum, R. y Veltkamp, R.C. (2004). Maximizing the area of overlap of two unions of disks under rigid motion. En 20th European Workshop on Computational Geometry, Sevilla.
Size: 234.6Kb
Format: PDF

URI: http://hdl.handle.net/11441/55071

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)