Bir birim diske uyan bir nokta kümesinin maksimum alt kümeleri
Bir set olduğunu varsayalım $P$ nın-nin $n$ uçaktaki noktalar ve izin ver $P_1, \dots, P_k$ farklı alt kümeleri olmak $P$ öyle ki tüm işaret ediyor $P_i$ herkes için bir birim diske sığar $i$, $1\le i\le k$.
Üstelik her biri $P_i$ maksimumdur, yani hiçbir birim diski bir alt kümeyi kapsayamaz $P$ bu katı bir üst kümesidir $P_i$. Görsel olarak konuşursak, kaplayan bir birim diskini hareket ettirirsek$P_i$ olmayan bir noktayı kapsamak $P_i$, daha sonra o diskin içindeki en az bir nokta açığa çıkacaktır.
İşte bir örnek:

Yukarıdaki şekilde, üç maksimum alt küme vardır.
Bu sorunun bir adı olup olmadığını veya daha önce çalışılmış olup olmadığını bilmiyorum ama işte sorularım.
- Yapabilmek $k$ göre üstel olmak $n$?
- Değilse, bu maksimum alt kümeleri polinom zamanı wrt içinde bulabilir miyiz? $n$?
Aşağıdaki argümandan dolayı üssel olarak bu tür çok sayıda alt küme olduğunu düşünüyorum:
Noktaların yarıçaplı bazı disklerin merkezleri olduğunu varsayalım.$1/2$. Bu tür noktaların bir alt kümesi bir birim diske sığarsa, bir klik oluştururlar. Bir disk setinde üssel olarak çok sayıda grup olduğu için, bu belirli nokta setinin bir birim diske uyan üssel olarak birçok maksimal altkümesi olmalıdır.
Yanıtlar
Bir fonksiyon tanımlayalım $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, setten birkaç puan döndürür $P$merkezde bir birim disk ile kaplanmıştır. $(x, y)$. Bu, parçalı sabit bir işlevdir ve etki alanının , kümedeki noktalara merkezlenmiş, birim disklerin tüm kesişimleri tarafından tanımlanan düzlemsel bir alt bölüm olarak düşünülebileceğini görmek kolaydır.$P$. Bu alt bölüm, köşeleri (= kesişme noktaları), kenarları (= dairesel yaylar) ve yüzleri (= düzlemin parçaları, burada fonksiyonun$f$aynı değeri döndürür). Bu yüzlerin bu değerle etiketlendiğini söyleyeceğiz .
Bu alt bölüm tarafından tanımlanan düzlemsel grafiğin 4 düzenli bir grafik olduğunu varsayacağız - bu yaygın bir varsayım, yani içindeki tüm noktalar $P$genel konumdadır (her kesişme noktası tam olarak iki daireye aittir). İçin böyle bir alt bölüme bir örnek$n=3$ Her yüz için etiketin (dış yüz dahil) kırmızı renkte gösterildiği yerdedir.

Maksimum alt kümelerinizi anladığım kadarıyla $P_i$komşu yüzlerin tüm etiketlerinden daha büyük etiketlere sahip olan bu alt bölümün bu tür yüzleriyle ilişkilendirilebilir . Bu, maksimal alt küme tanımınızda kullandığınız "hareketli disk" semantiğinizin bir tür statik yorumudur.
Tüm birim dairelerinin ikili olarak birbiriyle kesişmesi durumunda, alt bölüm mümkün olduğunca çok yüz içerecektir. Bu durumda gösterilebilir:
- köşe sayısı $n(n-1)$
- kenar sayısı $2n(n-1)$
- yüz sayısı $n(n-1)+2$
Yani sorularınızın cevapları şöyle olacaktır:
- Hayır, numara $k$ maksimal alt kümelerin yüzdesi: $O(n^2)$çünkü tüm yüzlerin sayısından fazla olamaz.
- Evet, tüm maksimum alt kümeler şurada bulunabilir: $O(n^3)$ saf tarama algoritması ile zaman.
Bu problemin ismine gelince - Ünite Disk Kapağı probleminin bazı varyasyonları ile ilgili olabilir gibi görünüyor.