점 집합의 최대값

Maxima of a point set
5개의 빨간 점은 모든 빨간색과 노란색 점의 집합의 최대치 입니다.음영 영역은 5개의 최대치 중 적어도 1개가 지배하는 포인트를 보여준다.

계산 기하학에서, S 점의 유한 집합에 있는 점 p는 좌표가 모두 p의 해당 좌표보다 크거나 같은 S에 다른 점 q가 없는 경우 최대점 또는 비지배점이라고 한다.점 집합 S의 최대치는 모두 S의 최대점이다.맥시마 또는 맥시마 세트 문제라고도 하는 모든 최대 지점을 찾는 문제는 볼록한 선체와 직교 볼록한 선체 문제의 변형으로서 연구되어 왔다.포인트 모음의 파레토 프론티어를 찾는 것과 맞먹으며, 복수의 통화 보유가 다른 개인의 상대적 부를 비교하는 것을 포함하는 어플리케이션에 근거해 허버트 프리먼에 의해 유동통화 문제로 불렸다.[1]

2차원

2차원의 포인트의 경우, 이 문제는 다음 단계를 수행하는 알고리즘에 의해 시간 O(n log n)로 해결할 수 있다.[1][2]

  • 좌표 치수 중 하나로 점 정렬(예: x-좌표)
  • 각 점에 대해, x 좌표에 의한 감소 순서에서, 해당 y 좌표가 이전에 처리된 점의 최대 y 좌표보다 큰지 여부를 검정한다. (첫 번째 점의 경우, 이것은 공허하게 참이다.)만약 그렇다면, 그 점을 최대 점 중 하나로 출력하고, 지금까지 본 것 중 가장 위대한 점으로 y 좌표를 기억하라.

점의 좌표를 정수로 가정할 경우, 정수 정렬 알고리즘을 사용하여 속도를 높여 정렬 알고리즘과 동일한 점증상 실행 시간을 가질 수 있다.[3]

삼차원

3차원 점의 경우, 다음 단계를 수행하는 2차원 점과 유사한 알고리즘을 사용하여 시간 O(n log n)의 최대 점을 다시 찾을 수 있다.

  • 좌표 치수 중 하나로 점 정렬(예: x-좌표)
  • 각 점의 경우, x 좌표에 의한 감소 순서에서 yz 평면에 대한 투영이 지금까지 처리된 점 집합의 투영 중 최대치인지 여부를 검정한다.만약 그렇다면, 그 점을 최대 점 중 하나로 출력하고, 지금까지 본 것 중 가장 위대한 점으로 y 좌표를 기억하라.

이 방법은 정적 3차원 점 세트의 최대 점 계산 문제를 동적 2차원 점 세트의 최대 점 유지의 하나로 줄인다.2차원 서브 문제는 균형 잡힌 바이너리 검색 트리를 사용하여 동적 포인트 세트의 최대값 집합을 유지함으로써 효율적으로 해결할 수 있다.이 데이터 구조를 이용하여 새로운 포인트가 기존 포인트에 의해 지배되는지를 시험하고, 새로운 포인트가 지배하는 이전에 지배하지 않았던 포인트를 찾아 제거하며, 포인트당 로그타임으로 최대 포인트 집합에 새로운 포인트를 추가할 수 있다.검색 트리 작동 횟수는 알고리즘의 과정에 걸쳐 선형적이므로 총 시간은 O(n log n)이다.[1][2]

정수 좌표가 있는 점의 경우 알고리즘의 첫 번째 부분인 점을 정렬하면 다시 정수 정렬을 통해 속도를 높일 수 있다.점들을 세 치수 모두로 구분하여 정렬할 경우, 두 좌표의 상대적 순서를 변경하지 않고 최대 점의 정체성을 변경하지 않고 좌표 값의 범위를 1에서 n까지의 범위로 줄일 수 있다.이렇게 좌표공간이 줄어든 후에는 균형 잡힌 이진수 검색 트리 대신 판 엠드 보아스 트리를 사용하여 동적 2차원 최대 포인트 세트를 유지하는 문제를 해결할 수 있다.알고리즘에 대한 이러한 변경은 실행 시간을 O(n log log n)로 단축시킨다.[3]

상위 치수

어떤 차원 d에서든 한 점이 다른 점을 지배하는지 모든 쌍을 시험하고, 지배하지 않는 점을 출력물로 보고함으로써 문제를 시간 O(dn2) 내에 해결할 수 있다.단, d가 3보다 큰 상수일 경우에는 O(n(log n)d − 3 log n)[4] log n)로 개선할 수 있다.무작위로 생성되는 점 집합의 경우 선형 시간 내에 문제를 해결할 수 있다.[5][6]

참조

  1. ^ a b c Preparata, Franco P.; Shamos, Michael Ian (1985), "Section 4.1.3: The problem of the maxima of a point set", Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, pp. 157–166, ISBN 0-387-96131-3.
  2. ^ a b Kung, H. T.; Luccio, F.; Preparata, F. P. (1975), "On finding the maxima of a set of vectors" (PDF), Journal of the ACM, 22 (4): 469–476, doi:10.1145/321906.321910, MR 0381379, S2CID 2698043.
  3. ^ a b Karlsson, Rolf G.; Overmars, Mark H. (1988), "Scanline algorithms on a grid", BIT Numerical Mathematics, 28 (2): 227–241, doi:10.1007/BF01934088, hdl:1874/16270, MR 0938390, S2CID 32964283.
  4. ^ Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), "Scaling and related techniques for geometry problems", Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84), New York, NY, USA: ACM, pp. 135–143, doi:10.1145/800057.808675, ISBN 0-89791-133-4, S2CID 17752833.
  5. ^ Bentley, Jon L.; Clarkson, Kenneth L.; Levine, David B. (1993), "Fast linear expected-time algorithms for computing maxima and convex hulls", Algorithmica, 9 (2): 168–183, doi:10.1007/BF01188711, MR 1202289, S2CID 1874434.
  6. ^ 다이, H.K.;장, XW(2004년),"최대치는 컴퓨팅에 대해 선형 expected-time 알고리즘 개선된", Farach-Colton, 마르틴(교육.), LATIN 2004년:.이론적 인포매틱스, 6일 라틴 아메리카 심포지엄, 부에노스 아이레스, 아르헨티나, 4월 58,2004년, 회보, 강의 노트 컴퓨터 과학으로, 2976 vol., 베를린:Springer-Verlag,를 대신하여 서명함. 181–192, doi:10.1007/978-3-540-24698-5_22, MR2095193.