계산적 기하학(computational geometry)에서, 점 S의 유한 집합(finite set)에서 점 p는 만약 그 좌표가 p의 해당 좌표보다 모두 크거나 같은 S에서 다른 점 q가 없으면 최대한(maximal) 또는 비-지배적(non-dominated)이라고 말합니다. 점 집합 S의 최댓값들(maxima of a point set S)은 S의 모든 최대한의 점입니다. 최댓값의 문제(problem of the maxima) 또는 최댓값 집합 문제(maxima set problem)라고도 하는 모든 최대한의 점을 찾는 문제는 볼록 껍질(convex hull)과 직교 볼록 껍질(orthogonal convex hull) 문제의 변형으로 연구되어 왔습니다. 그것은 점의 모음의 파레토 국경(Pareto frontier)을 찾는 것과 동등하고, 허버트 프리먼(Herbert Freeman)에 의해 개인의 상대적인 부를 다양한 통화 보유량을 비교하는 응용을 기반으로 하는 부동-통화 문제(floating-currency problem)라고 불렀습니다.
Two dimensions
이-차원에서 점에 대해, 이 문제는 다음 단계를 수행하는 알고리듬에 의해 시간 O(n log n)에서 풀 수 있습니다:
- 좌표 차원 중 하나 (말하자면, x-좌표)에서 점을 정렬합니다.
- 각 점에 대해, x-좌표에 의해 감소하는 순서에서, 그것의 y-좌표가 임의의 이전에 처리된 점의 최댓값 y-좌표보다 큰지 여부를 테스트합니다. (첫 번째 점에 대해, 이것은 공허하게 참(vacuously true)입니다). 만약 그렇다면, 최대한의 점 중 하나로 점을 출력하고, 지금까지 본 것 중 가장 큰 y-좌표를 기억하십시오.
만약 점의 좌표가 정수(integers)라고 가정되면, 이것은 정수 정렬(integer sorting) 알고리듬을 사용하여 정렬 알고리듬과 동일한 점근적 실행 시간을 갖도록 속도를 높일 수 있습니다.
Three dimensions
삼-차원에서 점에 대해, 다음 단계를 수행하는 이-차원 알고리듬과 유사한 알고리듬을 사용하여 시간 O(n log n)의 최대한의 점을 찾는 것이 다시 가능합니다:
- 좌표 차원 중 하나 (말하자면, x-좌표)에서 점을 정렬합니다.
- 각 점에 대해, x-좌표에 의해 감소하는 순서에서, yz 평면 위로의 투영이 지금까지 처리된 점의 집합의 투영 집합 중에서 최대한인지 여부를 테스트합니다. 만약 그렇다면, 최대한의 점 중 하나로 점을 출력하고 지금까지 본 것 중 가장 큰 y-좌표를 기억하십시오.
이 방법은 정적 삼-차원 점 집합의 최대한의 점을 계산하는 문제를 동적 이-차원 점 집합의 최대한의 점을 유지하는 문제로 줄입니다. 이-차원 하위-문제는 균형-잡힌 이진 탐색 트리(balanced binary search tree)를 사용하여 동적 점 집합의 최댓값의 집합을 유지함으로써 효율적으로 풀 수 있습니다. 이 데이터 구조를 사용하여, 새로운 점이 기존 포인트에 의해 지배되는지 여부를 테스트하고, 새로운 점에 의해 지배되는 이전에-지배적이지 않은 점을 찾아서 제거하고, 최대한의 점의 집합에 새로운 점을 추가하는 것이 점 당 로그 시간에서 가능합니다. 탐색 트리 연산의 숫자는 알고리듬 과정에 걸쳐 선형적이므로, 총 시간은 O(n log n)입니다.
정수 좌표를 갖는 점에 대해, 점을 정렬하는 알고리듬의 첫 번째 부분은 다시 정수 정렬을 통해 속도를 높일 수 있습니다. 만약 점이 세 차원 모두에 의해 개별적으로 정렬되면, 임의의 두 좌표의 상대적 순서를 변경하지 않고 최대한의 점의 항등식을 변경하지 않고도 좌표 값의 범위가 1에서 n 범위로 줄일 수 있습니다. 이렇게 좌표 공간을 축소한 후에는, 균형-잡힌 이진 탐색 트리 대신 van Emde Boas tree를 사용하여 최대한의 점의 동적 이-차원 집합을 유지하는 문제를 해결할 수 있습니다. 알고리듬에 대한 이들 변경은 실행 시간을 O(n log log n)로 가속화합니다.
Higher dimensions
임의의 차원 d에서, 그 문제는 하나가 또 다른 점을 지배하는지 여부에 대한 모든 점의 쌍을 테스트하고, 지배되지 않는 점을 출력으로 보고함으로써 시간 \(0(dn^2)\)에서 풀 수 있습니다. 어쨌든, d가 3보다 큰 상수일 때, 이것은 \(O(n(\log n)^{d-3} \log \log n)\)으로 개선될 수 있습니다. 무작위로 생성된 점 집합에 대해, 선형 시간(linear time)으로 문제를 해결하는 것이 가능합니다.
