求蜂窝图最大的蜂窝对称性.ppt

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,*,*,求蜂窩圖最大的蜂窩對稱性,對稱性:,以蜂窩22來看,其對稱數為 14=,max5,11,14 (,從三個軸來看)因此其最大對稱性為圖,C,1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,20,21,22,23,24,21,22,23,24,9,9,24,22,8,2,13,3,14,1,7,21,3,4,5,8,9,10,15,16,17,20,21,22,23,24,圖,A:5,個蜂窩,圖,B:11,個蜂窩,圖,C:14,個蜂窩,1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,18,20,23,本圖最大的蜂窩對稱性為,不考慮中空的蜂窩圖,1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,20,21,22,23,24,點座標,X,Y,Z,(1,0,0),(0,1,0),(0,0,1),(1,1,-1),(1,2,-1),演算法考量,每一個,cell,能確實地被找出來,蜂窩與蜂窩之間的相對位置,1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,20,21,22,23,24,Lemma 1,給定一個蜂窩圖,對於蜂窩圖上任何一個蜂窩,C,若已知,C,任意兩個邊,則可在常數時間內找出,C.,Definition-distance,1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,20,21,22,23,24,distance(3,4)=1,distance(3,9)=1,distance(3,22)=2,distance(3,24)=3,Lemma 2,給定一個蜂窩圖,已知蜂窩圖上兩個蜂窩,C,與,C,且,C,與,C,有邊相鄰,則,C,與,C,的相對位置可以在常數時間內找出.,C,C,a,b,c,d,e,f,g,h,i,j,up,down,C:a b c d e f,up,down,C:i h g b a j,up,down,C:a b g h i j,Algorithm,C,d=1,任意挑兩個相鄰的邊,e1,、,e2,找出包含,e1,、,e2,這兩個邊的蜂窩,C.,找出所有與蜂窩,C,距離為,d,的蜂窩,d=d+1,若存在蜂窩與,C,的距離為,d,則,回到,step 3.,否則結束.,Complexity of transformation,Space,C,為蜂窩個數,Time,n,