확률적 노이즈가 있는 기본 연산을 사용한 계산 기하학
2025-01-20
새로운 프리프린트는 확률적으로 노이즈가 있는 기본 연산 하에서의 계산 기하학 알고리즘을 탐구합니다. 이러한 많은 알고리즘은 입력 좌표에 접근하여 조합 정보로 변환하는 기본 연산에 의존합니다. 이 논문은 기본 연산이 무작위로 잘못된 결과를 생성하는 경우를 고려하고 효율성을 크게 저하시키지 않고 높은 확률로 정확한 결과를 얻는 방법을 조사합니다. 일부 문제(예: 볼록 껍질 생성)의 경우 반복으로 인한 속도 저하를 피할 수 있지만 다른 문제(예: 가장 가까운 점 쌍 찾기)의 경우에는 피할 수 없습니다. 이것은 효율성을 높이기 위해 노이즈가 있는 비교를 사용하는 이전의 통신 복잡도 연구와 관련이 있습니다.