| [ QuizWit ] in KIDS 글 쓴 이(By): mkjung (띠방탱이들) 날 짜 (Date): 2000년 6월 9일 금요일 오전 04시 49분 27초 제 목(Title): Re: 점들사이의 거리 2차원 좌표평면내에 유한한 넓이의 정사각형이 있고, 정사각형 안에 n개의 점이 있습니다. 점들을 A1, A2, ..., An 이라고 할 때, 서로간의 거리가 d 이하인 점의 쌍(Am, An)을 모두 찾고 싶습니다. 여기서 d << (정사각형의 한변의 길이) 라고 가정하면, O(n^2) 미만의 복잡도를 가지는 알고리즘이 있습니까? Divide & Conquer를 시도해봤는데 별로 깔끔해보이지 않아서.. -_-; =============== O(n^2) 이하의 컴퓨테이션타임을 가진 알고리듬은 존재할리가 없지요. 인간이 손으로 대충해도 pairwise comparision뿐이 먹히지 않으니까... 음.... 아무리 빨리해도 n(n-1)/2 step은 걸릴듯. 그러나 대가리를 다음과 같이 굴려보면 pairsiwe comparision없이! 알고리듬을 짤수있기에 O(n)을 이룩할수는 있을듯. 다음알고리듬은 probabilistic algorithm 이라 히히 pi/4 의 probability로 작동이되고 모든쌍을 찾아주지는 않습니다. ^^ 그냥 정사각형안에 내접하는 디빵 달덩이같은 원을 그리고 그원안에 들어있는 모든점들은 무조건 pairwise 위의 조건을 만족합니다. 그럼 귀탱이에 얌체처럼 재수없게 왕따당한 점들은어떻게 하냐구요? 그점에 인접한 정사각형의 모서리에서 d/\sqrt(2)의 반지름을 가진 원을그리면 quater circle이나올겁니다. 요 quater circle에서 가장먼점이 정확히 distance d 를가지고 요런 컨피규레이션가질 확률은 probability=0 거든요. 그럼 시메트리에 의해서 이런 쿼터 서끌이 4개 나오니까 각각에 대해 해주시고요, 위의 두가지 경우를 벗어나는경우는 4코너의 부스러기들사이끼리 거리가 d이하로 나오는경우인데 이런경우는 지금 우리가 2차원 메져공간에서 유한한 점가지고 장난치는거라 확률이 정확히 0 입니다. :) Hence, my probabilistic algorithm find such pairs in O(n) probabilistically. 음냐 또 사기쳤군... 우히히... 키즈의 정신박약 개구리들을 무찌르러 이땅에 태어나신 하늘같으신 인류의 영웅 씨방돼지를 받들어모시고, 얼굴 붉게 밝히고 귀염둥이 앞세우고 개구리잡이에 앞장서자. --- 키즈인들을 위한 어린이날 교시. |