¿Cuántos hiperplanos se necesitan para separar $n$ puntos en $\mathbb{R}^m$ ?

Question

Por "separado", quiero decir que cada punto se encuentra en su propia región/celda.

Por ejemplo, se necesita un mínimo de $P = 4$ líneas para separar $n = 7$ puntos en $\mathbb{R}^2$ ( $m=2$ ), suponiendo que no hay 3 puntos sobre una misma línea (es decir, que están en posición general):

( Heptágono regular )

Ahora, en general, al menos cuántos hiperplanos $P(m, n)$ se necesita para separar $n$ puntos en $\mathbb{R}^m$ (asumiendo la posición general)?

Answer 1

Esta cuestión fue analizada por Ralph P. Boland y Jorge Urrutia en el documento " Separación de colecciones de puntos en espacios euclidianos ”. Todavía no he leído este artículo. Según entendí, los autores mostraron que $$\lceil (n-1)/m\rceil\le P(m,n)\le \lceil(n-2^{\lceil\log m\rceil})/m\rceil+\lceil\log m\rceil,$$ y $P(2,n)=\lceil n/2\rceil$ .