| [ QuizWit ] in KIDS 글 쓴 이(By): jccha (잊으면그만) 날 짜 (Date): 1999년 2월 6일 토요일 오후 10시 45분 02초 제 목(Title): Re: computational geometry. 금방 생각나는데로 하면, 주어진 data를 n^3개의 cube로 생각하고, (x,y,z)에 아무 order (예: dictionary order)를 주어 이들 cube를 c_1,...c_{n^3} 으로 씁니다. 그리고, X_i = union of c_1,...c_{i-1} 이라고 합시다. x = 0 for i=1 to n^3 begin if (no faces of c_i meet X_i) x = x+1 /* 0-handle */ else if (c_i meets X_i in two opposite faces only) x = x-1 /* 1-handle */ else if (all but two opposite faces of c_i meet X_i) x = x+1 /* 2-handle */ else if (all faces of c_i meet X_i) x = x-1 /* 3-handle */ end 를 하면 x가 euler character이 되네요. c_i의 주변 cube 6개만 검사하면 X_i와 만나는 face를 세는 건 쉽지요? 그럼 o(n^3)인가요? 너무 느린가? pixel의 갯수를 n이라 했으면 o(n) 인데 :) 참, 위와 같이 하면 2차원의 10 과 같이 점(또는 3차원의 경우 변)에서만 만나는 01 경우는... 귀찮으니까 resolution을 높여서 그런 경우는 없다고 합시다 ^^; |