Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2012, Vol. 13 Issue (8): 559-564    DOI: 10.1631/jzus.C1200010
    
A note on circle packing
Young Joon Ahn, Christoph M. Hoffmann, Paul Rosen
Department of Mathematics Education, Chosun University, Gwangju 501-759, Korea; Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA; Scientific Computing and Imaging Institute, University of Utah, Salt Lake City, UT 84112, USA
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

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.

Key words： Circle packing      Algorithm performance      Parallel computation      Graphics processing unit (GPU)     
Received: 13 January 2012      Published: 02 August 2012
CLC:  TP391  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Young Joon Ahn
Christoph M. Hoffmann
Paul Rosen
Cite this article:

Young Joon Ahn, Christoph M. Hoffmann, Paul Rosen. A note on circle packing. Front. Inform. Technol. Electron. Eng., 2012, 13(8): 559-564.

URL:

http://www.zjujournals.com/xueshu/fitee/10.1631/jzus.C1200010     OR     http://www.zjujournals.com/xueshu/fitee/Y2012/V13/I8/559


A note on circle packing

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.

关键词： Circle packing,  Algorithm performance,  Parallel computation,  Graphics processing unit (GPU) 
[1] Gopi Ram , Durbadal Mandal , Sakti Prasad Ghoshal , Rajib Kar . Optimal array factor radiation pattern synthesis for linear antenna array using cat swarm optimization: validation by an electromagnetic simulator[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 570-577.
[2] Lin-bo Qiao, Bo-feng Zhang, Jin-shu Su, Xi-cheng Lu. A systematic review of structured sparse learning[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 445-463.
[3] Yuan-ping Nie, Yi Han, Jiu-ming Huang, Bo Jiao, Ai-ping Li. Attention-based encoder-decoder model for answer selection in question answering[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 535-544.
[4] Rong-Feng Zhang , Ting Deng , Gui-Hong Wang , Jing-Lun Shi , Quan-Sheng Guan . A robust object tracking framework based on a reliable point assignment algorithm[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 545-558.
[5] Wen-yan Xiao, Ming-wen Wang, Zhen Weng, Li-lin Zhang, Jia-li Zuo. Corpus-based research on English word recognition rates in primary school and word selection strategy[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 362-372.
[6] . A quality requirements model and verification approach for system of systems based on description logic[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 346-361.
[7] Ali Darvish Falehi, Ali Mosallanejad. Dynamic stability enhancement of interconnected multi-source power systems using hierarchical ANFIS controller-TCSC based on multi-objective PSO[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 394-409.
[8] Li Weigang. First and Others credit-assignment schema for evaluating the academic contribution of coauthors[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 180-194.
[9] Jun-hong Zhang, Yu Liu. Application of complete ensemble intrinsic time-scale decomposition and least-square SVM optimized using hybrid DE and PSO to fault diagnosis of diesel engines[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 272-286.
[10] Hui Chen, Bao-gang Wei, Yi-ming Li, Yong-huai Liu, Wen-hao Zhu. An easy-to-use evaluation framework for benchmarking entity recognition and disambiguation systems[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 195-205.
[11] Yue-ting Zhuang, Fei Wu, Chun Chen, Yun-he Pan. Challenges and opportunities: from big data to knowledge in AI 2.0[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 3-14.
[12] Bo-hu Li, Hui-yang Qu, Ting-yu Lin, Bao-cun Hou, Xiang Zhai, Guo-qiang Shi, Jun-hua Zhou, Chao Ruan. A swarm intelligence design based on a workshop of meta-synthetic engineering[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 149-152.
[13] Le-kui Zhou, Si-liang Tang, Jun Xiao, Fei Wu, Yue-ting Zhuang. Disambiguating named entities with deep supervised learning via crowd labels[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 97-106.
[14] Yong-hong Tian, Xi-lin Chen, Hong-kai Xiong, Hong-liang Li, Li-rong Dai, Jing Chen, Jun-liang Xing, Jing Chen, Xi-hong Wu, Wei-min Hu, Yu Hu, Tie-jun Huang, Wen Gao. Towards human-like and transhuman perception in AI 2.0: a review[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 58-67.
[15] Yu-xin Peng, Wen-wu Zhu, Yao Zhao, Chang-sheng Xu, Qing-ming Huang, Han-qing Lu, Qing-hua Zheng, Tie-jun Huang, Wen Gao. Cross-media analysis and reasoning: advances and directions[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 44-57.