Maximizing the Sum of Weights of Points in a Given Square
Jaehoon Kim · The Journal of the Korean Institute of Information and Communication Engineering · 2015
본 논문에서는 평면상에 가중치를 가진 점들이 주어질 때, 임의의 상수 r에 대해서 변의 길이 r인 정사각형 영역을 고려해서 이 안에 속하는 점들의 가중치 합이 최대가 되는 영역을 찾고자 한다. 변의 길이가 정해져 있지 않은 경우에 임의의 사각형 영역을 찾는 문제에 대한 연구가 있었다. 본 논문에서는 상수 r이 주어질 때, 변의 길이 r인 정사각형 영역을 찾는 문제를 다룬다. 우리는 동적 환경 하에서의 일차원 문제를 풀고, 이를 이용해서 O(n log n+m) 시간 복잡도를 갖는 알고리즘을 제안한다.