Full Text:   <2392>

CLC number: TP391

On-line Access: 2012-08-02

Received: 2012-01-13

Revision Accepted: 2012-06-21

Crosschecked: 2012-07-06

Cited: 0

Clicked: 3952

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2012 Vol.13 No.8 P.559-564


A note on circle packing

Author(s):  Young Joon Ahn, Christoph M. Hoffmann, Paul Rosen

Affiliation(s):  Department of Mathematics Education, Chosun University, Gwangju 501-759, Korea; more

Corresponding email(s):   ahn@chosun.ac.kr, cmh@cs.purdue.edu, prosen@sci.utah.edu

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

Share this article to: More |Next Article >>>

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

@article{title="A note on circle packing",
author="Young Joon Ahn, Christoph M. Hoffmann, Paul Rosen",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T A note on circle packing
%A Young Joon Ahn
%A Christoph M. Hoffmann
%A Paul Rosen
%J Journal of Zhejiang University SCIENCE C
%V 13
%N 8
%P 559-564
%@ 1869-1951
%D 2012
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1200010

T1 - A note on circle packing
A1 - Young Joon Ahn
A1 - Christoph M. Hoffmann
A1 - Paul Rosen
J0 - Journal of Zhejiang University Science C
VL - 13
IS - 8
SP - 559
EP - 564
%@ 1869-1951
Y1 - 2012
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1200010

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Andreatta, M., Bezdek, A., Boronski, J.P., 2011. The problem of Malfatti: two centuries of debate. Math. Intell., 33(1):72-76.

[2]Bern, M., Eppstein, D., 2000. Quadrilateral meshing by circle packing. Int. J. Comput. Geom. Appl., 10(4):347-360.

[3]Bottema, O., 2000. The Malfatti problem. Forum Geom., 1:43-50.

[4]Chiang, C.S., Hoffmann, C.M., Rosen, P., 2010. Hardware assistance for constrained circle constructions I: sequential problems. Comput. Aid. Des. Appl., 7(1):17-32.

[5]Chiang, C.S., Hoffmann, C.M., Rosen, P., 2012. A generalized Malfatti problem. Comput. Geom., 45(8):425-435.

[6]Collins, C.R., Stephenson, K., 2003. A circle packing algorithm. Comput. Geom., 25(3):233-256.

[7]Hoffmann, C.M., Joan-Arinyo, R., 2002. Parametric Modeling. In: Farin, G., Hoschek, J., Kim, M.S. (Eds.), Handbook of Computer Aided Geometric Design. Elsevier North Holland, Amsterdam.

[8]Kharevych, L., Springborn, B., Schroder, P., 2005. Discrete Conformal Mappings via Circle Patterns. ACM SIGGRAPH Courses, p.6.

[9]Lamure, H., Michelucci, D., 1995. Solving Geometric Constraints by Homotopy. Proc. Symp. on Solid Modeling and Applications, p.263-269.

[10]Liu, J., Xue, S., Liu, Z., Xu, D., 2009. An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle. Comput. Ind. Eng., 57(3):1144-1149.

[11]Lopez, C.O., Beasley, J.E., 2011. A heuristic for the circle packing problem with a variety of containers. Eur. J. Oper. Res., 214(3):512-525.

[12]Rodin, B., Sullivan, D., 1987. The convergence of circle packings to the Riemann mapping. J. Differ. Geom., 26:349-360.

[13]Stephenson, K., 2003. Circle packing: a mathematical tale. Notices Amer. Math. Soc., 50(11):1376-1388.

[14]Stephenson, K., 2005. Introduction to Circle Packing: the Theory of Discrete Analytic Functions. Cambridge University Press, New York.

[15]Wang, H., Huang, W., Zhang, Q., Xu, D., 2002. An improved algorithm for the packing of unequal circles within a larger containing circle. Eur. J. Oper. Res., 141(2):440-453.

[16]Willams, G.B., 2001. Approximation of quasisymmetries using circle packings. Discr. Comput. Geom., 25:103-124.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE