(UL)
-
Maximizing the area of overlap of two unions of disks under rigid motion [Elektronski vir]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: Preprint series. - ISSN 1318-4865 (Vol. 44, št. 1019, 2006, str. 1-20)Type of material - e-articlePublish date - 2006Language - englishCOBISS.SI-ID - 14786649
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Berg, Mark de | |
Cabello, Sergio | 25993 |
Giannopoulos, Panos | |
Knauer, Christian | |
Oostrum, René van | |
Weltkamp, Remco C. |
Source: Personal bibliographies
and: SICRIS
Select pickup location:
Material pickup by post
Delivery address:
Address is missing from the member's data.
The address retrieval service is currently unavailable, please try again.
By clicking the "OK" button, you will confirm the pickup location selected above and complete the reservation process.
By clicking the "OK" button, you will confirm the above pickup location and delivery address, and complete the reservation process.
By clicking the "OK" button, you will confirm the address selected above and complete the reservation process.
Notification
Automatic login and reservation service currently not available. You can reserve the material on the Biblos portal or try again here later.
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
Pickup location | Material status | Reservation |
---|
Reservation in progress
Please wait a moment.
Reservation was successful.
Reservation failed.
Reservation...
Membership card:
Pickup location: