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
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
 全文: PDF 
摘要： 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)    
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)
收稿日期: 2012-01-13 出版日期: 2012-08-02
CLC:  TP391  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Young Joon Ahn
Christoph M. Hoffmann
Paul Rosen

引用本文:

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

链接本文:

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

[1] Gopi Ram , Durbadal Mandal , Sakti Prasad Ghoshal , Rajib Kar . 使用猫群算法优化线性天线阵列的最佳阵因子辐射方向图：电磁仿真验证[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 570-577.
[2] Lin-bo Qiao, Bo-feng Zhang, Jin-shu Su, Xi-cheng Lu. 结构化稀疏学习综述[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 445-463.
[3] Yuan-ping Nie, Yi Han, Jiu-ming Huang, Bo Jiao, Ai-ping Li. 基于注意机制编码解码模型的答案选择方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 535-544.
[4] Rong-Feng Zhang , Ting Deng , Gui-Hong Wang , Jing-Lun Shi , Quan-Sheng Guan . 基于可靠特征点分配算法的鲁棒性跟踪框架[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 545-558.
[5] Wen-yan Xiao, Ming-wen Wang, Zhen Weng, Li-lin Zhang, Jia-li Zuo. 基于语料库的小学英语认识率及教材选词策略研究[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 362-372.
[6] . 一种基于描述逻辑的体系质量需求建模与验证方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 346-361.
[7] Ali Darvish Falehi, Ali Mosallanejad. 使用基于多目标粒子群算法多层自适应模糊推理系统晶闸管控制串联电容器补偿技术的互联多源电力系统动态稳定性增强器[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 394-409.
[8] Jun-hong Zhang, Yu Liu. 应用完备集合固有时间尺度分解和混合差分进化和粒子群算法优化的最小二乘支持向量机对柴油机进行故障诊断[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 272-286.
[9] Li Weigang. 用于评估共同作者学术贡献的第一和其他合作者信用分配模式[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 180-194.
[10] Hui Chen, Bao-gang Wei, Yi-ming Li, Yong-huai Liu, Wen-hao Zhu. 一种易用的实体识别消歧系统评测框架[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 195-205.
[11] 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. AI2.0时代的类人与超人感知：研究综述与趋势展望[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 58-67.
[12] 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. 跨媒体分析与推理：研究进展与发展方向[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 44-57.
[13] Yue-ting Zhuang, Fei Wu, Chun Chen, Yun-he Pan. 挑战与希望：AI2.0时代从大数据到知识[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 3-14.
[14] Bo-hu Li, Hui-yang Qu, Ting-yu Lin, Bao-cun Hou, Xiang Zhai, Guo-qiang Shi, Jun-hua Zhou, Chao Ruan. 基于综合集成研讨厅的群体智能设计研究[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 149-152.
[15] Le-kui Zhou, Si-liang Tang, Jun Xiao, Fei Wu, Yue-ting Zhuang. 基于众包标签数据深度学习的命名实体消歧算法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 97-106.