요즘에는 모처럼 계산기하 관련 코딩을 하고있다.

평면위에 원들이 있을때 각각의 원들을 일부라도 포함하는 가장 작은 원을 찾는 문제다.

(까만원들이 이렇게 문제로 주어졌을때,
모든 까만원의 일부라도 포함하거나 터치하는 원들 중 가장 작은 저 빨간 원을 찾으면 된다.)


재밌는건 원의 갯수를 n개라고 했을때,

이 문제는 n개의 원을 x축을 따라서 정렬하는것보다 빠르게 풀 수 있다는거다.(시간복잡도가 expected O(n))


재미없는건...

사실 논문으로 쓸때에는 99%의 지면을 할당하는 주요 알고리즘이 코드에서는 10%가량밖에 안되고

it's trivial 이라고 논문에 적은 1%에 해당하는 부분이 저 코드의 90%에 해당한다는거다.


예를들면 단순히 3개의 원을 터치하는 가장 작은 원을 찾는 trivial한 문제조차도

실제 구현하려면 비선형 연립 방정식을 풀어야한다.

논문에서는 매우 직관적이고 우아한 알고리즘이지만

구현은 지옥임.

근데 사실 굳이 이 문제만이 아니라 계산기하쪽 알고리즘들이 대부분 그런듯...


아무튼 이제 거의 구현해서 코드 돌리고 xml로 결과 뽑아서 ipe에서 열어봤더니 위에 그럼처럼 이쁘게 나온다.

이걸 열심히 구현한 공로(?)로 논문에 공저자로도 들어갈것 같으니 조만간 그간 노력한 보람이 있을듯하다.
저작자 표시
신고

'공부' 카테고리의 다른 글

언어의 모호성  (0) 2010.11.16
가변인수(va_arg)를 이용한 계산오차 줄이기  (3) 2010.08.02
계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
SQL injection on python+SQLite3  (0) 2010.04.02
Posted by youknow04


티스토리 툴바