@article{ART001630069},
author={김재각 and 김인범},
title={Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2012},
volume={17},
number={1},
pages={161-188}
TY - JOUR
AU - 김재각
AU - 김인범
TI - Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length
JO - Journal of The Korea Society of Computer and Information
PY - 2012
VL - 17
IS - 1
PB - The Korean Society Of Computer And Information
SP - 161
EP - 188
SN - 1598-849X
AB - In general, Euclidean minimum spanning tree is a tree connecting input nodes with minimum connecting cost. But the tree may not be optimal when applied to real world problems of three dimension. In this paper, three dimension Euclidean minimum spanning tree is proposed, connecting all input nodes of 3-dimensional space with minimum cost. In experiments for 30,000 input nodes with 100% space ratio, the tree produced by the proposed method can reduce 90.0% connection cost tree, compared with the tree by two dimension Prim's minimum spanning tree. In two dimension plane, the proposed tree increases 251.2% connecting cost, which is pointless in 3-dimensional real world. Therefore, the proposed method can work well for many connecting problems in real world space of three dimensions.
KW - Euclidean Minimum Spanning Tree;Space Ratio;3-Dimensional Space;Prim's MST Algorithm;Connecting Cost
DO -
UR -
ER -
김재각 and 김인범. (2012). Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length. Journal of The Korea Society of Computer and Information, 17(1), 161-188.
김재각 and 김인범. 2012, "Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length", Journal of The Korea Society of Computer and Information, vol.17, no.1 pp.161-188.
김재각, 김인범 "Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length" Journal of The Korea Society of Computer and Information 17.1 pp.161-188 (2012) : 161.
김재각, 김인범. Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length. 2012; 17(1), 161-188.
김재각 and 김인범. "Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length" Journal of The Korea Society of Computer and Information 17, no.1 (2012) : 161-188.
김재각; 김인범. Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length. Journal of The Korea Society of Computer and Information, 17(1), 161-188.
김재각; 김인범. Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length. Journal of The Korea Society of Computer and Information. 2012; 17(1) 161-188.
김재각, 김인범. Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length. 2012; 17(1), 161-188.
김재각 and 김인범. "Three Dimensional Euclidean Minimum Spanning Tree for Connecting Nodes of Space with the Shortest Length" Journal of The Korea Society of Computer and Information 17, no.1 (2012) : 161-188.
