| [ QuizWit ] in KIDS 글 쓴 이(By): pinkrose (Wenger) 날 짜 (Date): 1999년 2월 8일 월요일 오후 01시 27분 27초 제 목(Title): [ans] comp. geom. i haven't went thru jccha's algorithm but it looks OK and the running time is O(n^3) now. Unfortunately, it seems there are some redundancies in conditional statement. (if you let k=1, then it becomes 2D- problem and such redundancies become apprent.) I think the following method is the simplest. if A is the union of C_1 .. C_{n-1} then X(A U C_n) = X(A) + #vertex - #edge + #face - #cube ,where #vertex ... are the number of vertices increased when C_n is attaced. For dictionary ordering, there are only 3 possiblities. 1 face meet. 2 faces meet. 3 faces meet. Hence ONLY 3 'if' statements are all we need. In general, if we use N^d voxels to approximate d-dimensional compact manifold A, then X(N^d grid) --> X(A) as d --> infinity. By the way, who is LEE-BYUNG-LIM? I don't think this problem is worth publishing. :) They said "What sign can you give us to see, so that we may believe you?" |