Sottoinsiemi massimi di un insieme di punti che rientrano in un disco unitario

Question

Supponiamo che ci sia un insieme$P$di$n$punti sul piano, e lascia$P_1, \dots, P_k$essere sottoinsiemi distinti di$P$tale che tutti i punti in$P_i$si inserisce all'interno di un disco unitario per tutti$i$,$1\le i\le k$.

Inoltre, ciascuno$P_i$è massimale, cioè nessun disco unitario può coprire un sottoinsieme di$P$questo è un rigoroso sovrainsieme di$P_i$. Visivamente parlando, se spostiamo un disco unitario che copre$P_i$per coprire un punto non in$P_i$, allora almeno un punto che si trovava all'interno di quel disco verrà scoperto.

Ecco un esempio:

Nella figura sopra, ci sono tre sottoinsiemi massimi.

Non so se questo problema abbia un nome o sia stato studiato prima, ma ecco le mie domande.

1. Può$k$essere esponenziale rispetto a$n$?
2. In caso contrario, possiamo trovare quei sottoinsiemi massimali in tempo polinomiale wrt$n$?

Penso che ci siano esponenzialmente molti di questi sottoinsiemi a causa del seguente argomento:
Supponiamo che i punti siano centri di alcuni dischi con raggio$1/2$. Se un sottoinsieme di tali punti rientra in un disco unitario, allora formano una cricca. Poiché ci sono esponenzialmente molte cricche in un insieme di dischi, allora dovrebbero esserci esponenzialmente molti sottoinsiemi massimi di questo particolare insieme di punti che si adattano a un disco unitario.

Answer 1

Definiamo una funzione$f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, restituendo un numero di punti dal set$P$, coperto da un disco unitario con il centro in punta$(x, y)$. Questa è una funzione costante a tratti, ed è facile vedere che il suo dominio può essere pensato come una suddivisione planare, definita da tutte le intersezioni di dischi unitari, centrata in punti dell'insieme$P$. Questa suddivisione contiene vertici (= punti di intersezione), spigoli (= archi di cerchio) e facce (= pezzi del piano, dove la funzione$f$restituisce lo stesso valore). Diremo che queste facce sono etichettate da questo valore.

Supponiamo che il grafo planare, definito da questa suddivisione, sia un grafo 4-regolare - è un'assunzione comune, nel senso che tutti i punti in$P$sono in posizione generale (ogni punto di intersezione appartiene esattamente a due cerchi). Un esempio di tale suddivisione per$n=3$è sotto, dove l'etichetta per ogni faccia (compresa quella esterna) è mostrata in colore rosso.

Per quanto ho capito i tuoi sottoinsiemi massimi$P_i$può essere associato a tali facce di questa suddivisione, che hanno etichette più grandi di tutte le etichette delle loro facce vicine . È una specie di interpretazione statica della semantica del "disco in movimento", che hai usato nella definizione del sottoinsieme massimo.

La suddivisione conterrà quante più facce possibili nel caso in cui tutti i cerchi unitari si intersechino a coppie. Si può dimostrare che in questo caso:

• il numero di vertici è$n(n-1)$
• il numero di spigoli è$2n(n-1)$
• il numero di facce è$n(n-1)+2$

Quindi, le risposte alle tue domande saranno:

1. No, il numero$k$di sottoinsiemi massimali è$O(n^2)$, perché non può essere maggiore del numero di tutte le facce.
2. Sì, tutti i sottoinsiemi massimali possono essere trovati in$O(n^3)$tempo dall'ingenuo algoritmo di scansione.

Per quanto riguarda il nome di questo problema, sembra che possa essere correlato ad alcune varianti del problema Unit Disk Cover.