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.

Keywords: Circle packing, Algorithm performance, Parallel computation, Graphics processing unit (GPU)

Downloads

Download the Paper Download the BiBTeX

Citation

Young-Joon Ahn, Christoph Hoffmann, and Paul Rosen. A note on circle packing. Journal of Zhejiang University SCIENCE C, 13(8):559--564, August 2012. [ DOI ]

Bibtex


@article{Ahn.2012.ZUS,
  author = {Young-Joon Ahn and Christoph Hoffmann and Paul Rosen},
  title = {A Note on Circle Packing},
  journal = {Journal of Zhejiang University SCIENCE C},
  publisher = {SP Zhejiang University Press},
  volume = {13},
  number = {8},
  pages = {559-564},
  year = {2012},
  month = {August},
  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.},
  doi = {10.1631/jzus.C1200010},
  issn = {1869-1951},
  keywords = {Circle packing, Algorithm performance, Parallel computation, Graphics
	processing unit (GPU)}
}