A Note On Circle Packing
A Note On Circle Packing |
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.
Downloads
Citation
Young Joon Ahn, Christoph M Hoffmann, and Paul Rosen. A Note On Circle Packing. Journal of Zhejiang University SCIENCE C, 2012.
Bibtex
@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.} }