Loading...
Please wait, while we are loading the content...
Similar Documents
Kinetic Euclidean 2-centers in the Black-Box Model ⇤
| Content Provider | Semantic Scholar |
|---|---|
| Author | Berg, D. Roeloffzen, Mjm Marcel Speckmann, Bettina |
| Copyright Year | 2013 |
| Abstract | We study the 2-center problem for moving points in the plane. Given a set P of n points, the Euclidean 2-center problem asks for two congruent disks of minimum size that together coverP . Our methods work in the black-box KDS model, where we receive the locations of the points at regular time steps and we know an upper bound dmax on the maximum displacement of any point within one time step. We show how to maintain a (1 +")-approximation of the Euclidean 2-center in amortized sub-linear time per time step, under certain assumptions on the distribution of the point set P . In many cases|namely when the distance between the centers of the disks is relatively large or relatively small|the solution we maintain is actually optimal. |
| Starting Page | 173 |
| Ending Page | 176 |
| Page Count | 4 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://pure.tue.nl/ws/files/107881944/565579419325041.pdf |
| Alternate Webpage(s) | https://www.win.tue.nl/~mdberg/Papers/2013/brs-k2ce-13.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
