http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
두 평면 볼록집합의 겹치는 영역을 최대화하는 강체운동을 구하는 근사 알고리즘
박종대(Chong-Dae Park),신찬수(Chan-Su Shin),안희갑(Hee-Kap Ahn),정지원(Otfried Cheong),AntoineVigneron(Antoine Vigneron) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1
본 논문에서는 평면 상에 두 블록집합 P와 Q와 주어졌을 때, P를 강체운동 하에서 수평이동 및 회전이동하여 Q와 겹치는 영역이 근사적으로 최대가 되는 알고리즘을 제시한다. 임의의 양의 상수 ε이 주어졌을 때, 본 알고리즘은 가장 많이 겹치는 넓이의 1-ε 배를 보장하는 P의 겅체운동을 O(1/ε)번의 기하 질의와 O(1/ε²)log(1/ε) 시간 내에 구할 수 있다. 특히 P와 Q가 블록다각형일 때, O(1/ε)logn+(1/ε²)log(1/ε) 시간에 구한다. 만약 수평이동만 사용할 경우는 O((1/ε)log+(1/ε)log(1/ε)) 시간에 구할 수 있다.