2D에서 근접쌍 리스트를 구하는 가장 빠른 알고리즘은 뭘까요.
3173
points
points
2차원에서 모든 점의 최근접쌍 리스트를 만드는 가장 빠른 알고리즘이 뭘까요?
친구가 Delaunay 삼각분할 알고리즘을 소개해줬는데, 논문에 보니까 O(N^2) 이라고 되어있더군요.
(http://ouray.cudenver.edu/~rkyellur/5803/)
그래서야 그냥 루프를 2개 돌려서 구하는 것과 다를 바가 없지 않나요?
알고리즘을 배운적이 없다보니 어렵네요.
도와주세요!!
유용한 링크만 주셔도 감사하겠습니다.
내일은 도서관을 좀 뒤져봐야겠군요.
ps. 답글만 달다보니.. 제목을 그냥 태그로 썼군요.. 민망해라.
points
요구하는 바는 조금 다른 것 같은데...
삼각분할은 ACM-ICPC 에 제출해도 될 문제군요.
조금 읽어봤는데 삼각분할 algorithm 의 목표와 원하시는 바의 목표가 조금 다른 것 같네요.
대충봐도 삼각분할 algorithm 이 훨씬 어려워보입니다.
증명은 못하겠지만 원하시는 바에서 더 이상의 낮은 order 는 나올 것 같지 않습니다.
points
좀더 찾아봤더니
좀더 찾아봤더니 개선된 Delaunay 삼각분할 알고리즘은 NlnN이더군요.
클러스터링이 최종목적인데.. 클러스터링 알고르리즘들도 많이 있네요..
만만하게 보고 시작한일인데.. 공부할것이 많군요.