| [ QuizWit ] in KIDS 글 쓴 이(By): pinkrose (Wenger) 날 짜 (Date): 1999년 2월 8일 월요일 오후 05시 48분 37초 제 목(Title): [ans] computational geometry 01 10 이붙은경우 제공식은 맞습니다. 이문제 그냥 3차원 graph에서 꼭지점, 면, 변수등으로 오일러 케릭터리스틱 구하는 문제라고 생각하세요. 그래프상에서 오일러구할경우 접하는면하고의 공통되는게 무언지만 알면 (local representation) global한 성질을 구할수 있게됩니다. 3차원에서 딕셔너리 오더링을 쓰면 c_n 에 최대 3면이 붙습니다. 만약 이 세면에 붙는 cell들을 c_i,c_j,c_k 라한다면, c_i + c_j + c_k = 0,1,2,3 이 네가지 값중의 하나가 나옵니다. BECAUSE OF SYMMETRY, 면의붙는수가 같은경우는 반드시 오일러항은 같게 나와야합니다. 면이 하나나, 세개붙는경우는 configuration이 하나뿐이 없으니까 신경쓸필요가 없고 면이 2개붙는경우는 3차원상에서 시메트리쟌아요. 지적하신 8개에서 찾아야한다는건 좀 실수하신것같네요. 결국 오일러항은 삼차원에서 면의 갯수가 몇개붙는가의 함수로만 표현되지, 어떤면이 붙는지는 상관이 없습니다. 이차원에서도 이건 마찬가지입니다. 면두개중에서 왼쪽면이 붙든 위쪽면이 붙든 오일러항의 변화는 똑같쟌아요. -------------------------------------------------------- 문제는 01 10 이 연결되지 않은거라고 보는경우인데, 그래프이론상으로는 이걸 꼭지점을 통해서 연결되었다고 보기때문에 그래프이론에 근거한 제공식과 실제 오일러값과는 정확히 -1 or 0의 차이가 납니다.(2차원에서) -1 의 차이가 나는경우는 다음과 같습니다. 111 101 11* 와같이 대각이 비어있는경우 대각이 비어있지않으면 전혀 차이가 나지 않습니다. 이건 당연히 그래프이론에 근거하는 제 알고리듬때문에 그렇습니다. 111 101 11 이란그림에서 01 1 은 1 vertex를 서로 공유합니다. 이경우는 1을 더하셔야하고요, 비록 vertex 를 공유하지만 공유하지 않는척해야 합니다. 111 101 111 에서는 1을 빼주셔야합니다. 왜냐면 vertex를 3개의 쎌이 공유하기 때문에 inclusion & exclusion principle로 계산하면 한번을 빼줘야해요. 삼차원에서도 edge,vertex를 연결상태로 보지 않기때문에 조금더 복잡해지지만, 얼만큼 빼주는지 공식유도는 쉽습니다. inclusion & exclusion 프린시플을 잘이용하시면 이경우 modified euler characteristic을 유도하실수있습니다. 앗! 이건 새로운 QUIZ 로 냅시다. 아마 jccha씨알고리듬은 대각연결을 인정안하는상태에서 풀었기에 케이스가 무척 복잡해졌나보군요. 님이하신알고리듬은 코드가 너무 복잡해서 제가 제대로 이해를 못하겠던데, 좀 설명이 필요한것같군요. 히히.. 그래도 제가낸문제 열성적으로 참여하시는분이 있어서 뿌듯하군요. 홈페이지에 가봤는데, algebraic topology 하시는분이시군요. 그래서 handle이 나왔나보군요. ^^ 흠... 제가 이쪽분야가 아니라서 모르는게 하나 있는데, 잘되었군요. Betti Number에대해서 설명해주시면 고맙겠군요. 코호몰로지 어쩌고하면 잘모르니까, 아주쉽게.. 히히...베티넘버를 제일손쉽게 구할려면 어떻게 해야하는지도요. 이왕이면 실제적인 example을 가지고. 이왕이면 컴퓨테이션이 컴퓨터 임플리멘테이션이 가능한지도. They said "What sign can you give us to see, so that we may believe you?" |