Full Text:
<3331>
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: 6469
A note on circle packing
| |||||||||||||
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",
volume="13",
number="8",
pages="559-564",
year="2012",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1200010"
}
%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
TY - JOUR
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
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.
[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
<1>