Name
Abstract | ||
|---|---|---|
The internal diffusion limited aggregation (IDLA) process places n particles on the two dimensional integer grid. The first particle is placed on the origin; every subsequent particle starts at the origin and performs an unbiased random walk until it reaches an unoccupied position. In this work we study the computational complexity of determining the subset that is generated after n particles have been placed. We develop the first algorithm that provably outperforms the naive step-bystep simulation of all particles. Particularly, our algorithm has a running time of O(n log(2) n) and a sublinear space requirement of O(n(1/2) log n), both in expectation and with high probability. In contrast to some speedups proposed for similar models in the physics community, our algorithm samples from the exact distribution. To simulate a single particle fast we have to develop techniques for combining multiple steps of a random walk to large jumps without hitting a forbidden set of grid points. These techniques might be of independent interest for speeding up other problems based on random walks. |
Year | Venue | Field |
|---|---|---|
2014 | Lecture Notes in Computer Science | Growth model,Computer graphics (images),Computer science |
DocType | Volume | ISSN |
Conference | 8572 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Karl Bringmann | 1 | 427 | 30.13 |
| Fabian Kuhn | 2 | 2709 | 150.17 |
| Konstantinos Panagiotou | 3 | 290 | 27.80 |
| Ueli Peter | 4 | 34 | 4.28 |
| Henning Thomas | 5 | 35 | 3.96 |