기하 스패너

기하학적 스패너, t-스패너 그래프 또는 t-스패너는 고정 매개변수 t에 대한 정점 쌍 사이에 t-경로가 있는 정점으로서 점 집합에 걸쳐 가중 그래프로서 초기에 도입되었다. t-경로는 끝점 사이의 공간 거리의 최대 t배인 가중치를 가진 그래프를 통과하는 경로로 정의된다.매개변수 t를 스패너의 스트레치 계수 또는 팽창 계수라고 한다.^[1]

연산 기하학에서는 L.P에 의해 처음 개념이 논의되었다.1986년, 비록 "스패너"라는 용어는 원래 종이에 쓰이지 않았지만,^[2] 씹어라.

그래프 스패너의 개념은 그래프 이론에서 알려져 있다: t-스패너는 유사한 확장 특성을 가진 그래프의 하위 그래프를 확장하고 있다. 여기서 그래프 정점 사이의 거리는 그래프 이론적 용어로 정의된다.따라서 기하학적 스패너는 해당 메트릭에 내장된 정점 사이의 거리와 동일한 에지 가중치를 갖는 평면에 내장된 완전한 그래프의 그래프 스패너다.

스패너는 일부 근접성 문제를 해결하기 위해 계산 기하학에서 사용될 수 있다.그들은 또한 모션 계획, 통신망, 네트워크 신뢰성, 모바일 네트워크 로밍의 최적화 등과 같은 다른 분야에서의 응용 프로그램도 발견했다.

다양한 스패너 및 품질 측정

스패너의 품질을 분석하는 데 사용할 수 있는 여러 가지 방법이 있다.가장 일반적인 측정은 에지 카운트, 총 중량 및 최대 정점 수준이다.이러한 측정에 대한 점증상 최적 값은 $O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle$ O$(n)}$ 에지$$, O${\displaystyle }$( ${\displaystyle \mathrm{M}}$ S ${\displaystyle T)}$ ${\displaystyle$ O$($$MST)}$ 무게$$ $및{\displaystyle }$ O${\displaystyle }$( 1${\displaystyle }$) ${\displaystystyle$O(1$)}$ 최대도$$(여기서 MST는 최소 스패닝 트리의 무게를 나타낸다.)이다.

최대 m 모서리가 있는 n개 지점에 대해 최소 확장이 가능한 유클리드 평면에서 스패너를 찾는 것은 NP-경도인 것으로 알려져 있다.^[3]

다양한 품질 측정에서 뛰어난 스패너 알고리즘이 존재한다.빠른 알고리즘에는 WSPD 스패너와 Theta 그래프가 포함되며, 이 그래프는 둘 $다{\displaystyle }$ O${\displaystyle (n}$ log $){\displaystyle O(n\log$ n$)}$시간$$ 내에 선형 에지 수를 가진 스패너를 구성한다.더 좋은 무게와 정점 정도가 요구되는 경우 탐욕 스패너는 거의 2차 시간 내에 계산될 수 있다.

테타 그래프

Theta 그래프 $또는{\displaystyle \mathrm{}}$ or ${\displaystyle \Teta }$ -그래프는 콘 기반 스패너 계열에 속한다.기본 구성 방법은 각 꼭지점 주위의 공간을 원뿔 집합으로 분할하는 것을 포함하며, 원뿔 집합은 그래프의 나머지 정점을 분할한다.$Yao{\displaystyle \mathrm{}}$ Graphs와 마찬가지로$display$ {\displaystyle $\Teta }$ -그래프는$$ 원뿔당 하나의 가장자리를 포함하며, 여기서 차이가 나는 것은 해당 가장자리를 선택하는 방법이다.Yao Graphs는 그래프의 미터 공간에 따라 가장 가까운 정점을 선택하지만, $Ⅱ{\displaystyle \mathrm{}}$ ${\displaystyle \Theta }$그래프는$$ 각 원뿔 안에 포함된 고정 광선(컨벤션적으로 원뿔의 이등분자)을 정의하고 그 광선에 대한 직교 투영 투영과 관련하여 가장 가까운 이웃을 선택한다.

욕심쟁이 스패너

탐욕스러운 스패너 또는 탐욕스러운 그래프는 t-경로 없이 가장 가까운 점 쌍 사이에 엣지를 반복적으로 추가하는 그래프로 정의된다.이 그래프를 계산하는 알고리즘을 욕심 많은 스패너 알고리즘이라고 한다.그 공사로부터 탐욕스러운 그래프가 t-spanner라는 것을 사소한 것으로 따르게 된다.

탐욕스러운 스패너(spanner)는 처음에 고탐 다스의^[4] 박사 논문과 회의 논문^[5], 그리고 그 이후의 저널 논문에 인고 알트호퍼 외 에 의해^[6] 기술되었다.이들 출처는 마샬 베른(미공개)이 같은 건축물을 독자적으로 발견했다고도 했다.

탐욕스러운 스패너는 점증적으로 최적의 에지 카운트, 총 중량 및 최대 정점도를 달성하고 이러한 측정치에 대해 실제로 가장 잘 수행한다.$O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle O(n^{2}\logn)}$시간$$$$ 동안 O${\displaystyle (}$n 2${\displaystyle {}^{}}$) ${\displaystyle O(n^{2})$ 공간을 사용하여 $구성$할 수 있다.^[7]

딜라우나이 삼각측량

츄의 주요 결과는 평면의 점 집합에 대해 이 점 세트의 삼각형이 있어서 어떤 두 점에 대해서도 두 점 사이의 유클리드 거리 최대 1$$ ${\displaystyle 0\mathrm{}}$ ${\displaystyle {\sqrt{1}}의$길이로 삼각형의 가장자리를 따라 경로가 있다는 것이었다.그 결과는 장애물 중 최단 경로의 합리적인 근사치를 찾기 위한 움직임 계획에 적용되었다.

유클리드 델라우나이 삼각측량에서 알려진 가장 좋은 상한은 정점에 대한 a $({\displaystyle 4\mathrm{}}$ ${\displaystyle 3}$/ 9${\displaystyle }$)${\displaystyle \pi }$ ${\displaystyle 2.418}$ ${\displaystyle${($4{\sqrt{3}/9)\pi }\약 2.418}$ -spanner라는$$ 것이다.^[8]하한선은 $\pi {\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\$개에서$$ 조금 넘는 1.5846개로 늘어났다.^[9]

잘 구분된 쌍분해

스패너는 다음과 같은 방법으로 잘 분리된 쌍 분해로 구성될 수 있다.Construct the graph with the point set ${\displaystyle S}$ as vertex set and for each pair ${\displaystyle \{A,B\}}$ in a WSPD, add an edge from an arbitrary point ${\displaystyle a\in A}$ to an arbitrary point ${\displaystyle b\in B}$. Note that the resulting graph has a linear number of edges becauwSPD는 쌍의 선형 수를 가진다.^[10]

그에$$ 따라 잘 분리된 쌍 분해의 분리 파라미터를 선택하면 $t{\displaystyle }$ ${\displaystyle t}$에 대한 임의 값을 얻을 수 있다.

참조