Show simple item record

Presentation

dc.creatorBerg, Mark dees
dc.creatorCabello Justo, Sergioes
dc.creatorGiannopoulos, Panoses
dc.creatorKnauer, Christianes
dc.creatorOostrum, René vanes
dc.creatorVeltkamp, Remco C.es
dc.date.accessioned2017-03-02T07:40:50Z
dc.date.available2017-03-02T07:40:50Z
dc.date.issued2004
dc.identifier.citationBerg, 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.
dc.identifier.urihttp://hdl.handle.net/11441/55071
dc.description.abstractLet 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.es
dc.description.sponsorshipDutch Technology Foundationes
dc.description.sponsorshipMarie Curie Fellowship (Eurpoean Comission programme "Combinatorics, Geometry and Computation")es
dc.formatapplication/pdfes
dc.language.isoenges
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectGeometric optimizationes
dc.subjectApproximation algorithmses
dc.subjectShape matchinges
dc.subjectArea of overlapes
dc.subjectUnions of diskses
dc.subjectRigid motionses
dc.titleMaximizing the area of overlap of two unions of disks under rigid motiones
dc.typeinfo:eu-repo/semantics/conferenceObjectes
dc.type.versioninfo:eu-repo/semantics/submittedVersiones
dc.rights.accessrightsinfo:eu-repo/semantics/openAccesses
dc.relation.projectIDUIF 5055es
dc.relation.projectIDHPMT-CT-2001-00282es
idus.format.extent4 p.es
dc.eventtitle20th European Workshop on Computational Geometryes
dc.eventinstitutionSevillaes

FilesSizeFormatViewDescription
Maximizing the area of overlap ...234.6KbIcon   [PDF] View/Open  

This item appears in the following collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Except where otherwise noted, this item's license is described as: Attribution-NonCommercial-NoDerivatives 4.0 Internacional