A note on circle packing

Young Joon AHN; Christoph M. HOFFMANN; Paul ROSEN

doi:10.1631/jzus.C1200010

Your Location：

Home >

Browse articles >

A note on circle packing

Computer & Automation | Updated：2022-05-19

- A note on circle packing
- A note on circle packing
- Frontiers of Information Technology & Electronic Engineering Vol. 13, Issue 8, Pages: 559-564(2012)
- Affiliations：
  
  1.Department of Mathematics Education, Chosun University, Gwangju 501-759, Korea
  2.Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA
  3.Scientific Computing and Imaging Institute, University of Utah, Salt Lake City, UT 84112, USA
- Author bio：
  
  [ "Young Joon AHN, E-mail: ahn@chosun.ac.kr" ]
  [ "Christoph M. HOFFMANN, E-mail: cmh@cs.purdue.edu" ]
  [ "Paul ROSEN, E-mail: prosen@sci.utah.edu" ]
- Funds：
- DOI：10.1631/jzus.C1200010
  CLC： TP391
- Received：13 January 2012，
  
  Revised：2012-;7-;6，
  
  Published：2012-08
- Accepted：
Scan QR Code
Young Joon AHN, Christoph M. HOFFMANN, Paul ROSEN. A note on circle packing[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(8): 559-564.
DOI：

Young Joon AHN, Christoph M. HOFFMANN, Paul ROSEN. A note on circle packing[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(8): 559-564. DOI： 10.1631/jzus.C1200010.

摘要

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

references

M. Andreatta , , , A. Bezdek , , , J. P. Boroski . . The problem of Malfatti: two centuries of debate . . Math. Intell. , , 2011 . . 33 ( ( 1 ): ): 72 - - 76 . . DOI: 10.1007/s00283-010-9154-7 http://doi.org/10.1007/s00283-010-9154-7 . .

M. Bern , , , D. Eppstein . . Quadrilateral meshing by circle packing . . Int. J. Comput. Geom. Appl. , , 2000 . . 10 ( ( 4 ): ): 347 - - 360 . . DOI: 10.1142/S0218195900000206 http://doi.org/10.1142/S0218195900000206 . .

O. Bottema . . The Malfatti problem . . Forum Geom. , , 2000 . . 1 43 - - 50 . . . .

C.S. Chiang , , , C.M. Hoffmann , , , P. Rosen . . Hardware assistance for constrained circle constructions I: sequential problems . . Comput. Aid. Des. Appl. , , 2010 . . 7 ( ( 1 ): ): 17 - - 32 . . DOI: 10.3722/cadaps.2010.17-32 http://doi.org/10.3722/cadaps.2010.17-32 . .

C.S. Chiang , , , C.M. Hoffmann , , , P. Rosen . . A generalized Malfatti problem . . Comput. Geom. , , 2012 . . 45 ( ( 8 ): ): 425 - - 435 . . DOI: 10.1016/j.comgeo.2010.06.005 http://doi.org/10.1016/j.comgeo.2010.06.005 . .

C.R. Collins , , , K. Stephenson . . A circle packing algorithm . . Comput. Geom. , , 2003 . . 25 ( ( 3 ): ): 233 - - 256 . . DOI: 10.1016/S0925-7721(02)00099-8 http://doi.org/10.1016/S0925-7721(02)00099-8 . .

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

L. Kharevych , , , B. Springborn , , , P. Schrder . . Discrete Conformal Mappings via Circle Patterns . . ACM SIGGRAPH Courses , , 2005 . . p.6 DOI: 10.1145/1198555.1198665 http://doi.org/10.1145/1198555.1198665 . .

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

J. Liu , , , S. Xue , , , Z. Liu , , , D. Xu . . An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle . . Comput. Ind. Eng. , , 2009 . . 57 ( ( 3 ): ): 1144 - - 1149 . . DOI: 10.1016/j.cie.2009.05.010 http://doi.org/10.1016/j.cie.2009.05.010 . .

C.O. Lpez , , , J.E. Beasley . . A heuristic for the circle packing problem with a variety of containers . . Eur. J. Oper. Res. , , 2011 . . 214 ( ( 3 ): ): 512 - - 525 . . DOI: 10.1016/j.ejor.2011.04.024 http://doi.org/10.1016/j.ejor.2011.04.024 . .

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

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

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

H. Wang , , , W. Huang , , , Q. Zhang , , , D. Xu . . An improved algorithm for the packing of unequal circles within a larger containing circle . . Eur. J. Oper. Res. , , 2002 . . 141 ( ( 2 ): ): 440 - - 453 . . DOI: 10.1016/S0377-2217(01)00241-7 http://doi.org/10.1016/S0377-2217(01)00241-7 . .

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

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰