Sous-ensembles maximaux d'un ensemble de points qui tiennent dans un disque unitaire

Aug 19 2020

Supposons qu'il existe un ensemble$P$de$n$points sur le plan, et laissez$P_1, \dots, P_k$être des sous-ensembles distincts de$P$telle que tous les points de$P_i$s'adapte à l'intérieur d'un disque unitaire pour tous$i$,$1\le i\le k$.

De plus, chaque$P_i$est maximal, c'est-à-dire qu'aucun disque unitaire ne peut couvrir un sous-ensemble de$P$qui est un sur-ensemble strict de$P_i$. Visuellement parlant, si on déplace un disque unité qui couvre$P_i$couvrir un point qui n'est pas dans$P_i$, alors au moins un point qui était à l'intérieur de ce disque sera découvert.

Voici un exemple:

Dans la figure ci-dessus, il y a trois sous-ensembles maximaux.

Je ne sais pas si ce problème a un nom ou a été étudié auparavant, mais voici mes questions.

  1. Boîte$k$être exponentiel par rapport à$n$?
  2. Sinon, pouvons-nous trouver ces sous-ensembles maximaux en temps polynomial wrt$n$?

Je pense qu'il existe un nombre exponentiel de sous-ensembles de ce type à cause de l'argument suivant :
supposons que les points sont les centres de certains disques de rayon$1/2$. Si un sous-ensemble de ces points tient dans un disque unitaire, alors ils forment une clique. Puisqu'il y a un nombre exponentiel de cliques dans un ensemble de disques, il devrait y avoir un nombre exponentiel de sous-ensembles maximaux de cet ensemble particulier de points qui rentrent dans un disque unitaire.

Réponses

4 HEKTO Sep 03 2020 at 02:43

Définissons une fonction$f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, renvoyant un certain nombre de points de l'ensemble$P$, recouvert d'un disque unité dont le centre est au point$(x, y)$. Il s'agit d'une fonction constante par morceaux, et il est facile de voir que son domaine peut être considéré comme une subdivision plane, définie par toutes les intersections de disques unitaires, centrées en des points de l'ensemble$P$. Cette subdivision contient les sommets (= points d'intersection), les arêtes (= arcs de cercle) et les faces (= parties du plan, où la fonction$f$renvoie la même valeur). Nous dirons que ces faces sont étiquetées par cette valeur.

Nous supposerons que le graphe planaire, défini par cette subdivision, est un graphe 4-régulier - c'est une hypothèse courante, ce qui signifie que tous les points de$P$sont en position générale (chaque point d'intersection appartient à exactement deux cercles). Un exemple d'une telle subdivision pour$n=3$est ci-dessous, où l'étiquette de chaque face (y compris la face externe) est affichée en rouge.

Pour autant que je comprenne vos sous-ensembles maximaux$P_i$peuvent être associés à de telles faces de cette subdivision, qui ont des étiquettes plus grandes que toutes les étiquettes de leurs faces voisines . C'est une sorte d'interprétation statique de votre sémantique "disque mobile", que vous avez utilisée dans votre définition du sous-ensemble maximal.

La subdivision contiendra autant de faces que possible dans le cas où tous les cercles unitaires se coupent deux à deux. On peut montrer que dans ce cas :

  • nombre de sommets est$n(n-1)$
  • le nombre d'arêtes est$2n(n-1)$
  • le nombre de visages est$n(n-1)+2$

Ainsi, les réponses à vos questions seront :

  1. Non, le numéro$k$des sous-ensembles maximaux est$O(n^2)$, car il ne peut pas être supérieur au nombre de tous les visages.
  2. Oui, tous les sous-ensembles maximaux peuvent être trouvés dans$O(n^3)$temps par algorithme de balayage naïf.

Quant au nom de ce problème - il semble qu'il puisse être lié à certaines variantes du problème de couverture de disque d'unité.