단위 디스크에 맞는 포인트 세트의 최대 서브 세트
세트가 있다고 가정합니다. $P$ 의 $n$ 비행기에 포인트를두고 $P_1, \dots, P_k$ 구별되는 부분 집합 $P$ 모든 점이 $P_i$ 모두를위한 하나의 단위 디스크에 적합 $i$, $1\le i\le k$.
또한, 각각 $P_i$ 즉, 단위 디스크가 $P$ 그것은 엄격한 상위 집합입니다 $P_i$. 시각적으로 말하면, 우리가 커버하는 단위 디스크를 이동하면$P_i$ 포함되지 않은 지점을 커버하기 위해 $P_i$, 그러면 해당 디스크 내부에 있던 하나 이상의 지점이 발견됩니다.
다음은 그 예입니다.
위의 그림에는 세 개의 최대 부분 집합이 있습니다.
이 문제에 이름이 있는지 또는 이전에 연구 된 것인지는 모르겠지만 여기에 내 질문이 있습니다.
- 할 수있다 $k$ 기하 급수적이다 $n$?
- 그렇지 않다면 다항식 시간 wrt에서 최대 부분 집합을 찾을 수 있습니다. $n$?
나는 다음과 같은 주장으로 인해 기하 급수적으로 많은 부분 집합이
있다고 생각합니다. 점이 반경을 가진 일부 디스크의 중심이라고 가정합니다.$1/2$. 이러한 점의 하위 집합이 단위 디스크에 맞으면 파벌을 형성합니다. 디스크 세트에는 기하 급수적으로 많은 파벌이 있으므로 단위 디스크에 맞는이 특정 포인트 세트의 최대 서브 세트가 기하 급수적으로 많아야합니다.
답변
함수를 정의합시다 $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, 세트에서 여러 포인트를 반환 $P$, 중심이 지점에있는 단위 디스크로 덮여 있음 $(x, y)$. 이것은 부분적으로 상수 함수이며, 그 영역은 세트의 지점을 중심으로하는 단위 디스크의 모든 교차로 정의되는 평면적 세분화로 생각 될 수 있음을 쉽게 알 수 있습니다.$P$. 이 세분화에는 꼭지점 (= 교차점), 모서리 (= 원호) 및면 (= 평면 조각이 포함됩니다.$f$같은 값을 반환). 이 얼굴은 이 값 으로 레이블 이 지정 됩니다.
우리는이 세분화로 정의 된 평면 그래프가 4- 정규 그래프라고 가정 할 것입니다. 이것은 일반적인 가정입니다. $P$일반적인 위치에 있습니다 (각 교차점은 정확히 두 개의 원에 속합니다). 에 대한 그러한 세분의 예$n=3$ 아래에 각 얼굴 (외부 얼굴 포함)의 라벨이 빨간색으로 표시됩니다.
내가 당신의 최대 부분 집합을 이해하는 한 $P_i$인접한면의 모든 레이블보다 큰 레이블이있는이 세분화의 이러한면과 연관 될 수 있습니다 . 그것은 최대 부분 집합의 정의에서 사용한 "이동 디스크"의미론에 대한 일종의 정적 인 해석입니다.
세분화에는 모든 단위 원이 쌍으로 교차하는 경우 가능한 한 많은면이 포함됩니다. 이 경우 다음과 같이 표시 될 수 있습니다.
- 정점의 수는 $n(n-1)$
- 모서리 수는 $2n(n-1)$
- 얼굴의 수는 $n(n-1)+2$
따라서 귀하의 질문에 대한 답변은 다음과 같습니다.
- 아니, 번호 $k$ 최대 하위 집합의 $O(n^2)$, 모든 얼굴의 수보다 많을 수 없기 때문입니다.
- 예, 모든 최대 하위 집합은 $O(n^3)$ 순진한 스캐닝 알고리즘으로 시간.
에 관해서는 이름 이 문제의 -이 단위 디스크 커버 문제의 일부 변동과 관련이있을 수 있습니다 것 같습니다.