파라메트릭 검색

조합 최적화를 위한 알고리즘의 설계 및 분석에서 파라메트릭 검색은 니모드 메가도(1983)가 의사결정 알고리즘(이 최적화 문제가 주어진 임계값보다 더 나은 품질을 가진 솔루션을 가지고 있는가)을 최적화 알고리즘으로 변환하기 위해 발명한 기법이다(최상의 솔루션 찾기).계산 기하학의 최적화 문제를 해결하는 데 자주 사용된다.

테크닉

파라메트릭 검색의 기본 아이디어는 숫자 $파라미터$ X ${\displaystyle X$ 를 입력으로 하는 테스트 알고리즘을 (알 수 없는) 최적의 솔루션 $X^{*}$ X $X^{*}$ ${\$ 을 입력으로 $X^{*}$ 하여 실행하는 것처럼 시뮬레이션하는 것이다.이 테스트 알고리즘은 $X=X^{*}$ = $X=X^{*}$ $X=X^{*}$ ${\$ X $=X$ 일 때 불연속적으로 동작하고, X $X$ 을(를 $)$ 다른 계산값과 $X$ $단순$ 비교하거나 $X$ ${\displaystyle X$ 의 저도 다항 함수의 기호를 Si에 시험하는 것으로 $X$ $X$ 한다.시뮬레이션된 알고리즘의 $X$ ${\displaystyle$ X $}$ 을(를) 알 수 없음에도 불구하고 이러한 비교 또는 테스트 각각을 시뮬레이션해야 한다.각 비교를 시뮬레이션하기 위해 파라메트릭 검색은 다른 숫자 파라미터 $Y$ $Y$ 을(를 $Y$ 입력하는 것으로서 $Y$ $Y$ 이(가) 최적의 $Y$ 솔루션 $X^{*}$ X $X^{*}$ ${\$ X $^{*}$ 보다 위인지 아래인지 또는 같은지를 결정하는 두 번째 알고리즘인 의사결정 알고리즘을 적용한다 $X^{*}$

의사결정 알고리즘 자체는 $X^{*}$ X $∗{\$ 에서 불연속적으로 동작하므로, 동일한 알고리즘을 시험 알고리즘으로도 사용할 수 있다 $X^{*}$ 그러나 많은 애플리케이션은 다른 테스트 알고리즘(종종 비교 정렬 알고리즘)을 사용한다.매개변수 검색 기법의 고급 버전은 병렬 알고리즘을 테스트 알고리즘으로 사용하고, 의사결정 알고리즘의 인스턴스화 수를 유의하게 줄이기 위해 시뮬레이션해야 하는 비교를 일괄적으로 분류한다.

순차 테스트 알고리즘

파라메트릭 검색 기법의 가장 기본적인 형태에서, 테스트 알고리즘과 의사결정 알고리즘 모두 순차(비병렬) 알고리즘으로, 아마도 서로 동일한 알고리즘일 것이다.기법은 ( $알$ 수 없는) 최적의 솔루션 $값$ 을 매개 변수 X {\displaystyle X $}$ 로 지정했을 때 실행될 것처럼 단계별로 테스트 알고리즘을 시뮬레이션한다 $X$ 시뮬레이션이 매개 $변수$ X $X$ 을(를) 다른 숫자 $Y$ ${\displaystyty Y}$ 와 $X$ 비교하는 단계에 도달할 때마다 이 기술은 성능을 발휘할 수 없다 $Y$ $이$ 단계는 X $X$ 이(가) 무엇인지 $X$ 모르기 때문에 수치 비교를 통해 수행할 수 있다.대신 $파라미터$ Y $Y$ 를 가진 의사결정 알고리즘을 호출하고, 의사결정 알고리즘의 결과를 사용하여 비교의 출력을 결정한다.이러한 방식으로 시뮬레이션 시간은 결국 시험과 의사결정 알고리즘에 대한 시대의 산물을 동일시하게 된다.시험 알고리즘은 최적의 솔루션 값에서 불연속적으로 동작한다고 가정하기 때문에, 결정 알고리즘에 $Y$ 전달된 파라미터 값 $Y$ $Y$ 중 하나가 실제로 최적의 솔루션 값과 동일하지 않는 한 정확하게 시뮬레이션할 수 없다.이 경우 의사결정 알고리즘은 동등성을 검출하고 이후 출력에 대한 최적 솔루션 값을 저장할 수 있다.테스트 알고리즘이 $X$ $X$ 에서 다항식의 부호를 알아야 하는 경우, 이는 알 수 없는 솔루션 값이 이러한 루트 중 하나인지 또는 아닐 경우 두 루트 사이에 있는지 결정하기 위해 다항식의 루트를 의사결정 알고리즘에 전달하여 다시 시뮬레이션할 수 있다 $X$

메가도(1983년)와 반 우스트럼 & 벨트캄프(2002년)가 모두 같은 선을 따라 다른 일정한 속도로 우측으로 이동하는 홀수 수의 입자를 고려한 예다.입자의 중위수는 또한 우측 방향의 움직임을 가지지만 다른 시간에 다른 입자가 중위수가 되기 때문에 일정한 속도를 가지기 보다는 조각처럼 선형이 된다.처음에는 입자, 그리고 그 중간값들이 선의 원점 왼쪽에 있고, 결국 입자와 그 중간값들은 모두 원점 오른쪽에 있게 될 것이다.문제는 중위수가 정확히 원점에 있는 시간 $t_{0}$ $t_{0}$ 0 ${\$ 을 계산하는 것이다.선형 시간 결정 알고리즘은 정의하기 쉽다: $t$ 든지 $t$ ${\displaystyle$ t $t$ 시간 t $t$ 에서 각 입자의 위치를 계산하고 $t$ 원점 양쪽에 있는 입자의 수를 셀 수 있다.만약 여기 왼쪽에서 오른쪽보다 더 많은 입자들, 있어<>t 0{\displaystyle t<, t_{0}}, 오른쪽에는 왼쪽보다 더 많은 입자들, 있어 을, t 0{\displaystyle t>, t_{0}}. 이 결정 알고리즘의 각 단계는 하나 o.는 시간을 입력 매개 변수 t{\displaystyle지}를 비교하f는 parti씨족이 기원을 가로지르다

이 결정 알고리즘을 파라메트릭 검색의 테스트 알고리즘과 의사결정 알고리즘 둘 다로 사용하면 2차 총시간에서 $t_{0}$ 의 $t_{0}$ 시간 $t_{0}$ 0 ${\$ 을 찾기 위한 알고리즘이 도출된다.매개변수 $t_{0}$ $t_{0}$ ${\$ 에 대한 결정 알고리즘을 시뮬레이션하려면 $t_{0}$ 시뮬레이션은 각 입자에 대해 해당 교차 $t_{0}$ 이 t $t_{0}$ {\ $displaystyle t_{0$ 의 이전인지 이후인지, 따라서 t ${\$ 에 대한 원점의 왼쪽 또는 오른쪽에 있는지 여부를 결정해야 한다 $t_{0}$ 이 qu에 응답한다.단일 입자에 대한 에스티온 - 미지의 최적 교차 시간 t $t_{0}$ {\ $displaystyle t_{0}}$ 과(와) 비교 - 입자에 대한 교차 시간을 매개변수로 하여 동일한 결정 알고리즘을 실행함으로써 수행할 수 있다. $t_{0}$ 따라서 시뮬레이션은 각 입자 교차 시간에 대한 결정 알고리즘을 실행하게 되며, 그 중 하나가 최적의 교차 시간이어야 한다.결정 알고리즘을 한 번 실행하면 선형 시간이 걸리므로 각 교차 시간에 별도로 실행하면 2차 시간이 걸린다.

병렬 테스트 알고리즘

메가도(1983)가 이미 관측한 바와 같이, 파라메트릭 검색 기법은 효율적인 병렬 알고리즘으로 시뮬레이션 테스트 알고리즘을 대체함으로써 실질적으로 속도를 높일 수 있다. 예를 들어 병렬 컴퓨팅의 PRAM(Parallel Random-Access Machine) 모델에서 프로세서의 모음이 공유 메모리에서 동기식으로 동작하는 경우, 모두 performi.ng 다른 메모리 주소에 대한 동일한 작업 순서.테스트 알고리즘이 $PRAM$ 알고리즘이 P ${\disp} 프로세서$ 를 $P$ 사용하고 T ${\displaystyle$ T $}($ $각$ 프로세서가 단일 작업을 수행하는 T $T$ 단계 $T$ ) $T$ 를 사용하는 경우, 결정 알고리즘을 사용하여 각 단계를 시뮬레이션하여 최대 $P$ ${\disp$ }의 결과를 결정할 수 있다. $레이스타일 P}$ 의 $P$ 수치 비교.평가해야 할 비교 집합에서 중위수 또는 중위수에 가까운 값을 찾아 이 단일 값을 의사결정 알고리즘에 전달함으로써 의사결정 알고리즘의 단일 호출만으로 비교의 절반 또는 거의 절반을 제거할 수 있다. $이러한$ 방식으로 시뮬레이션에서 요구되는 비교 세트를 반씩 반복적으로 반감함으로써, 아무것도 남지 않을 때까지 의사결정 알고리즘에 대한 O( $O(\log P)$ $O(\log P)$ ) ${\displaystyle O(\log$ P $)}$ 호출만을 $O(\log P)$ 사용하여 P $P$ 수치 $P$ 비교 결과를 시뮬레이션할 수 있다.Thus, the total time for parametric search in this case becomes $O(PT)$ (for the simulation itself) plus the time for $O(T\log P)$ calls to the decision algorithm (for $T$ batches of comparisons, taking $O(\log P)$ calls 배치당).흔히 이러한 방법으로 해결할 수 있는 문제에 대해 PRAM 알고리즘의 시간 프로세서 제품은 순차적 의사결정 알고리즘의 시간과 비교가 되며, 병렬 시간은 다변량(polylogarithmic)이므로 다변량 인자에 의해서만 결정 알고리즘보다 속도가 느린 파라메트릭 검색의 총 시간이 발생한다.

$n$ $n$ 이동 $n$ 입자의 중위수 교차 시간을 찾는 예제의 경우 알고리즘의 매개변수로 주어진 시간에 입자의 위치를 정렬하는 병렬 정렬 알고리즘으로 순차 테스트 알고리즘을 대체한 다음 정렬된 순서를 사용하여 중위수를 결정할 수 있다.입자를 내어 그 위치의 기호를 찾다이 알고리즘에 대한 최선의 선택은 (실제로는 아닐지라도 이론 분석에 따르면) 아제타이, 콤일로스, 스제메레디(1983)의 분류 네트워크다.이는 프로세서의 숫자 $P$ $P$ $P$ 이 $n$ 가) 입력 $길이$ n $n$ 에 비례하고, 병렬 스텝 수는 로가리듬인 PRAM 알고리즘으로 해석할 수 있다.따라서 이 알고리즘을 순차적으로 시뮬레이션하는 데는 $O(\log n)$ $O(\log n)$ $O(\log n)$ $O(n\log n)$ $O(n\log n)$ $O(\log n)$ $){\displaystyle O(n\log$ $n$ $)}$ 과(와) $O(\log n)$ $O(n\log n)$ ${$ n $O(\log n)$ ){\ $displaystyle$ $O$ (\log n $)}$ batch와 $O(\log n)$ 함께 시뮬레이션 자체에 대한 $O(n\log n)$ 시간 O(n\ $displaystystyle O(log$ n)가 $O(\log n)$ 을 선형 시간 결정 알고리즘으로 $O(\log n)$ 호출할 수 있다. $O(n\log ^{2}n)$ 시간 범위를 함께 설정하면 O $O(n\log ^{2}n)$ $O(n\log ^{2}n)$ $O(n\log ^{2}n)$ ⁡ $O(n\log ^{2}n)$ ) $O(n\log ^{2}n)$ 개의 파라메트릭 검색 총 시간이 주어진다 $O(n\log ^{2}n)$ .이것은 이 문제에 대한 최적의 시간이 아니다 – 같은 문제는 중앙값의 교차 시간이 입자의 교차 시간의 중앙값과 같다는 것을 관찰함으로써 더 빨리 해결될 수 있다 – 그러나 동일한 기법을 다른 복잡한 최적화 문제에도 적용할 수 있으며, 많은 경우 가장 빨리 알려진 다항식을 제공한다.이러한 문제에 대한 일알 알고리즘.

AKS 정렬 네트워크 분석에서 발생하는 상수 요인이 크기 때문에 이 네트워크를 테스트 알고리즘으로 사용한 파라메트릭 검색은 실용적이지 않다.대신 판 우스트럼 & 벨트캄프(2002)는 퀵소트의 병렬 형태(입력을 반복적으로 두 개의 서브셋으로 분할한 다음 각 서브셋을 재귀적으로 정렬하는 알고리즘)를 사용할 것을 제안한다.이 알고리즘에서, 파티션 단계는 대량으로 평행하며(각 입력 요소는 선택된 피벗 요소와 비교되어야 한다) 두 개의 재귀 호출은 서로 병렬로 수행될 수 있다.결과 파라메트릭 알고리즘은 최악의 경우 AKS 정렬 네트워크에 기반한 알고리즘보다 느리다.그러나 반 우스트럼과 벨트캄프는 (이러한 결과에 의해 해결되지 않은 비교만 의사결정 알고리즘에 대한 추가 호출로 이어질 수 있도록) 과거 의사결정 알고리즘의 결과가 저장되고 시뮬레이션된 테스트 알고리즘에 의해 테스트된 비교 값이 충분히 균등하게 분포되어 있다면, 알고리즘이 진행됨에 따라 이 알고리즘이 충분히 균등하게 분포되어 있다고 주장한다.각 시간 단계에서 생성되는 미해결 비교의 수는 적을 것이다.이러한 경험적 경험적 분석과 알고리즘의 구현에 근거한 실험 결과에 기초하여, 그들은 퀵소트 기반의 파라메트릭 검색 알고리즘이 최악의 경우 분석이 시사하는 것보다 더 실용적일 것이라고 주장한다.

비동기화 정렬

콜(1987)은 테스트 알고리즘이 비교 정렬 알고리즘인 사례(예: 예)에 대해 파라메트릭 검색 기법을 더욱 최적화했다.AKS 정렬 네트워크와 그 자리에 사용할 수 있는 다른 정렬 알고리즘을 위해, Cole은 시뮬레이션 프로세서를 서로 동기화할 필요는 없다고 본다. 대신, 어떤 프로세서는 정렬 알고리즘을 통해 더 멀리 진행하도록 허용할 수 있고, 다른 프로세서는 비교 결과가 단념되기를 기다릴 수 있다.ned. 이 원리에 기초하여, 콜은 분류 알고리즘의 시뮬레이션을 수정하여, 모두 테스트 알고리즘의 동일한 병렬 시간 단계에서 나오지 않을 수 있는 미해결 시뮬레이션 비교 컬렉션을 유지한다.파라메트릭 검색의 동기화된 병렬 버전에서와 같이 중위 비교 값을 찾아 이 값에 대한 결정 알고리즘을 호출함으로써 이러한 비교의 절반을 해결할 수 있다.그런 다음, 해결되지 않은 비교의 컬렉션이 공허해질 때까지 이 반감 절차를 반복하는 대신, 콜은 해결되어야 할 또 다른 비교에 도달할 때까지 해결된 비교를 기다리던 프로세서가 시뮬레이션을 통해 진전되도록 한다.콜은 이 방법을 사용하여 메기도의 원래 버전의 파라메트릭 검색에서 이루어지는 O $O(\log ^{2}n)$ $O(\log ^{2}n)$ ⁡ $O(\log ^{2}n)$ $){\displaystyle O(\log ^{2}n)$ 호출 $O(\log ^{2}n)$ 대신, 테스트 알고리즘이 정렬하는 파라메트릭 검색 알고리즘을 결정 알고리즘에 대한 로그 번호로만 완료할 수 있음을 보여준다.AKS 정렬 네트워크를 사용하는 대신 콜(1988년)의 병렬 병합 정렬 알고리즘과 이 기술을 결합하는 것도 가능하여, 그러나 여전히 실용적일 만큼 작지 않은 더 작은 상수 인자와 시간 한계가 있다.(AKS 정렬 네트워크가 그렇듯이) Cole의 기술이나 복수의 계산 경로를 시뮬레이션하는 관련 기법에 의해 (Fernandez-Baca 2001) 경계의 분산 컴퓨팅 네트워크에서 계산될 수 있는 문제에 대해서도 유사한 속도 향상을 얻을 수 있다.

Goodrich & Pszona(2013년)는 콜의 이론적 향상과 밴 우스트럼 & 벨트캄프(2002년)의 실용적인 스피드 업을 결합했다.반 우스트럼과 벨트캄프가 그랬던 것처럼 병렬 퀵소트를 사용하는 대신, 그들은 Reischuk(1985)이 개발한 퀵소트의 변종인 박스소트를 사용한다. 이 퀵소트는 파티셔닝 단계가 입력을 단지 두 개의 하위문제 $O({\sqrt {n}})$ 에 $O({\sqrt {n}})$ O ( $){\displaysty$ O $({\sqrt{n}})}}}$ 개의 $O({\sqrt {n}})$ 작은 하위문제들로 임의로 분할한다.콜의 기법에서와 같이, 그들은 비동기화된 파라메트릭 검색을 사용한다. 이 검색에서는 시뮬레이션된 병렬 정렬 알고리즘의 실행의 각 개별 스레드가 다른 비교의 결과를 결정할 필요가 있을 때까지 진행될 수 있고, 미해결된 비교의 횟수가 중위수 비교값과 calli를 찾아 반감된다.ng 해당 값을 갖는 의사결정 알고리즘.그들이 보여주듯이, 결과 무작위화된 파라메트릭 검색 알고리즘은 콜의 이론적 분석과 일치하는 높은 확률로 의사결정 알고리즘에 대한 로그 번호만 만든다.그들의 논문의 확장 버전은 알고리즘의 구현에 따른 실험 결과를 포함하는데, 이것은 몇 가지 자연적인 기하학적 최적화 문제에 대한 이 방법의 총 실행 시간이 가장 잘 동기화된 파라메트릭 검색 구현의 총 실행 시간(van Oostrum 및 Veltkamp의 퀵소트 기반 방법)과 유사하다는 것을 보여준다.어떤 문제에서는 더 빨리, 어떤 문제에서는 조금 더 느리게 대처한다.그러나 의사결정 알고리즘에 대한 호출의 수는 상당히 적으므로, 이 방법은 의사결정 알고리즘이 더 느린 파라메트릭 검색의 적용에서 더 큰 이익을 얻을 수 있을 것이다.

점의 중위수 교차시간을 찾는 예문 문제에 대해서는 콜의 알고리즘과 굿리히와 프조나의 알고리즘이 모두 $O(n\log n)$ O $O(n\log n)$ ( $O(n\log n)$ log $){\displaystyle O(n\log$ n $)}$ 를 얻는다 $O(n\log n)$ 굿리치와 프조나의 경우 알고리즘이 랜덤화되어 이 시간을 높은 확률로 얻는다.

이진 검색과 비교

이분법(이진법)은 의사결정을 최적화로 변환하는 데도 사용할 수 있다.이 방법에서는 최적의 솔루션 값을 포함하고 있는 것으로 알려진 수간격의 간격을 유지하고, 통화 결과에 따라 중간값의 결정 알고리즘을 호출하고 중간값의 반간격만 위아래로 유지함으로써 간격을 반복적으로 축소한다.이 방법은 최적 솔루션 값에 대한 수치적 근사치만 찾을 수 있지만, 이 근사치의 정확도 비트의 수에 비례하는 의사결정 알고리즘에 대한 다수의 호출에서 그렇게 함으로써 약하게 다항 알고리즘을 생성한다.

대신, 해당될 경우 파라메트릭 검색은 강력한 다항식 알고리즘을 찾는데, 이 알고리즘의 실행 시간은 입력 크기의 함수일 뿐이며 숫자 정밀도와는 무관하다.그러나 파라메트릭 검색은 로그보다 더 클 수 있는 (결정 알고리즘에 비해) 시간 복잡성의 증가를 초래한다.약하게 다항식이라기보다는 강하게 다항식이기 때문에 파라메트릭 검색에 기반한 알고리즘은 이론적인 관점에서 더 만족스럽다.실제로 바이너리 검색은 빠르고 구현이 훨씬 간단하기 때문에 파라메트릭 검색을 실용화하기 위한 알고리즘 엔지니어링 노력이 필요하다.그럼에도 불구하고, van Oostrum & Veltkamp(2002)는 "단순 이항 검색 접근법이 파라메트릭 검색의 실질적인 대체 방법으로 주장되는 경우가 많지만, 그들이 수행한 실험 비교에서 우리의 [모수 검색] 알고리즘에 의해 능가된다"고 쓰고 있다.

적용들

단순 선형 회귀 분석과 비교한 테일-센 추정기

파라메트릭 검색은 특히 연산 기하학(Agarwal, Sharir & Toledo 1994)에 최적화 문제에 대한 효율적인 알고리즘 개발에 적용되었다.여기에는 다음이 포함된다.

유클리드 공간에 설정된 점의 중심점은 중심점을 포함하는 모든 반쪽 공간도 입력 점의 일정한 부분을 포함하는 점이다. $d$ $d$ -차원 $d$ 공간의 경우 달성할 수 있는 최적 분율은 항상 $1/(d+1)$ 1 $1/(d+1)$ / $1/(d+1)$ ( $1/(d+1)$ + 1 $1/(d+1)$ ) ${\displaystyle$ 1 $/(d+1)$ 이며 $1/(d+1)$ 2차원 중심점을 구성하기 위한 파라메트릭-검색 기반 알고리즘은 나중에 다른 알고리즘 기법을 사용하여 선형 시간으로 개선되었다.그러나 이러한 개선은 더 높은 차원으로 확대되지 않는다.3차원에서는 파라메트릭 검색을 사용하여 시간 $O(n^{2}\log ^{4}n)$ $O(n^{2}\log ^{4}n)$ $O(n^{2}\log ^{4}n)$ $O(n^{2}\log ^{4}n)$ $){\displaystyle O(n^{2}\log ^{4}n)}($ Cole 1987)에서 중심점을 찾을 수 있다.
파라메트릭 검색은 테일-센 추정기에 대한 $O(n\log n)$ $O(n\log n)$ $){\displaystyle O(n\log n)}$ 시간 $O(n\log n)$ 알고리즘의 기초로 사용할 수 있으며, 이는 단순한 선형 회귀보다 특이치에 훨씬 덜 민감한 점 집합에 라인을 적합시키기 위한 강력한 통계 방법이다(Cole et al. 1989).
컴퓨터 그래픽에서, 광선 촬영 문제(특정 시선 또는 광선에 교차하는 장면의 첫 번째 물체 결정)는 파라메트릭 검색과 단순한 문제를 위한 데이터 구조를 결합하여 주어진 장애물 집합이 특정 레이를 포함하는지 시험함으로써 해결할 수 있다(Agarwal & Matoushek 1993).
가장 큰 스틱 문제는 주어진 다각형 안에 있는 가장 긴 선 세그먼트를 찾는 것이다.파라메트릭 검색 기반 알고리즘(Agarwal, Sharir & To Leedo 1994) $\epsilon >0$ 을 사용하여 $n$ $n$ -측면 $n$ 다각형 및 $\epsilon >0$ > 0 $\epsilon >0$ 에 대해 $O(n^{8/5+\epsilon })$ O $O(n^{8/5+\epsilon })$ $O(n^{8/5+\epsilon })$ / $O(n^{8/5+\epsilon })$ + $O(n^{8/5+\epsilon })$ ) $O(n^{8/5+\epsilon })$ {\ $displaystyle$ O( $n^{8/5+\$ pisplaystylon $}).$
주어진 점 집합을 포함하고 가능한 가장 작은 폭(내측 및 외측 반지름의 차이)을 갖는 환율을 점 집합의 원형도를 측정하는 데 사용할 수 있다. $다시$ 말하지만, 이 문제는 파라메트릭 검색(Agarwal, Sharir & & Toledo 1994 $\epsilon >0$ 기반 알고리즘을 사용하여 n $n$ 측 $n$ 다각형 및 $\epsilon >0$ > $\epsilon >0$ $\epsilon >0$ 에 대해 $O(n^{8/5+\epsilon })$ O $O(n^{8/5+\epsilon })$ $O(n^{8/5+\epsilon })$ / $O(n^{8/5+\epsilon })$ + $O(n^{8/5+\epsilon })$ ) $O(n^{8/5+\epsilon })$ {\ $displaystyled$ O( $n{8/5+\$ displaystylon })에서 해결할 수 있다.
The Hausdorff distance between translates of two polygons, with the translation chosen to minimize the distance, can be found using parametric search in time $O((mn)^{2}\log ^{3}mn)$ , where $m$ and $n$ are the numbers of sides of the polygons (Agarwal, Sharir & Toledo 1994).
$두$ 폴리곤 체인 사이의 프레셰 거리는 $O(mn\log mn)$ O $O(mn\log mn)$ $O(mn\log mn)$ $O(mn\log mn)$ $O(mn\log mn)$ n $){\displaystyle$ O $(mn$ $\$ $log mn)}$ 의 파라메트릭 검색을 사용하여 계산할 수 있으며 $O(mn\log mn)$ 여기서 m {\ $displaystyle m}$ 과 $m$ n $n$ 은 $n$ 곡선의 세그먼트 수입니다(Alt & Godau 1995).
유클리드 평면에서 $n$ 한 속도로이동하는 n {\ $displaystyle n}$ 포인트의 $n$ 경우, $O(n\log ^{2}n)$ $O(n\log ^{2}n)$ $O(n\log ^{2}n)$ ⁡ $O(n\log ^{2}n)$ $){\displaystyle$ O $(n\log ^{2}n)}$ 시간에서 가장 작은 지름(및 당시의 직경)을 얻는 시간을 찾을 수 있다 $O(n\log ^{2}n)$ 파라메트릭 검색도 다른 용도로 사용할 수 있다.최소 주변 공 크기 또는 최대 신장 트리의 중량을 포함한 측정의 경우 이동 지점 세트의 일부 측정치가 최소값을 얻는 시간을 구하는 유사한 문제(Fernández-Baca 2001).