여러 개의 원이 있을 때, 가장 많이 겹치는 부분에서 겹치는 원의 개수를 빠르게 구할 수 있을까?

예를 들어 레이더를 설치하려고 하는데, 가장 많은 기지국과 통신할 수 있는 위치를 찾을 때 궁금할 수 있는 부분이다.

모든 부분집합에 대한 NP문제로 해결하는 건 말이 안 된다. 삼각분할도 생각해볼 수는 있다. 지금까지 내가 생각해본 최적의 방법은 반원을 ordered set에 넣는 스위핑 기법이다.

원을 세로로 잘라 왼쪽 원과 오른쪽 원을 만든 후 ordered set에 넣는다. 두 원의 교점에서 이벤트가 발생하면 원의 순서를 바꾼다.

그림 설명 1

그림 설명 2