A Note On Circle Packing

The problem of packing circles into a domain of prescribed topology is considered. The circles need not have equal radii. The Collins-Stephenson algorithm computes such a circle packing. This algorithm is parallelized in two different ways and its performance is reported for a triangular, planar domain test case. The implementation uses the highly parallel graphics processing unit (GPU) on commodity hardware. The speedups so achieved are discussed based on a number of experiments.

Young Joon Ahn, Christoph M Hoffmann, and Paul Rosen. A Note On Circle Packing. Journal of Zhejiang University SCIENCE C, 2012.

@article{ahn2012note,
  title = {A Note on Circle Packing},
  author = {Ahn, Young Joon and Hoffmann, Christoph M and Rosen, Paul},
  journal = {Journal of Zhejiang University SCIENCE C},
  volume = {13},
  pages = {559--564},
  year = {2012},
  keywords = {Circle packing, Algorithm performance, Parallel computation, Graphics
processing unit (GPU)},
  abstract = {The problem of packing circles into a domain of prescribed topology is
    considered. The circles need not have equal radii. The Collins-Stephenson algorithm
    computes such a circle packing. This algorithm is parallelized in two different ways and
    its performance is reported for a triangular, planar domain test case. The
    implementation uses the highly parallel graphics processing unit (GPU) on commodity
    hardware. The speedups so achieved are discussed based on a number of experiments.}
}